 Covering moving points with anchored disksC. Bautista-Santiago, J.M. Díaz-Báñez, R. Fabila-Monroy, D. Flores-Peñaloza, D. Lara and J. Urrutia European Journal of Operational Research, 2012, vol. 216, issue 2, 278-285 Abstract: Consider a set of mobile clients represented by n points in the plane moving at constant speed along n different straight lines. We study the problem of covering all mobile clients using a set of k disks centered at k fixed centers. Each disk exists only at one instant and while it does, covers any client within its coverage radius. The task is to select an activation time and a radius for each disk such that every mobile client is covered by at least one disk. In particular, we study the optimization problem of minimizing the maximum coverage radius. First we prove that, although the static version of the problem is polynomial, the kinetic version is NP-hard. Moreover, we show that the problem is not approximable by a constant factor (unless P=NP). We then present a generic framework to solve it for fixed values of k, which in turn allows us to solve more general optimization problems. Our algorithms are efficient for constant values of k. Keywords: Combinatorial optimization; Covering algorithms; Mobile objects; Client–server communication; Computational geometry (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:216:y:2012:i:2:p:278-285 DOI: 10.1016/j.ejor.2011.07.048 Access Statistics for this article European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati More articles in European Journal of Operational Research from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.