Name
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. (C) 2011 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.ejor.2011.07.048 | European Journal of Operational Research |
Keywords | Field | DocType |
Combinatorial optimization,Covering algorithms,Mobile objects,Client–server communication,Computational geometry | Mobile client,Mathematical optimization,Polynomial,Computational geometry,Combinatorial optimization,Optimization problem,Mathematics | Journal |
Volume | Issue | ISSN |
216 | 2 | 0377-2217 |
Citations | PageRank | References |
1 | 0.36 | 29 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Crevel Bautista-Santiago | 1 | 5 | 1.31 |
| José Miguel Díaz-Báñez | 2 | 193 | 26.65 |
| Ruy Fabila Monroy | 3 | 48 | 16.57 |
| David Flores-Peñaloza | 4 | 32 | 6.44 |
| Dolores Lara | 5 | 7 | 2.50 |
| Jorge Urrutia | 6 | 1064 | 134.74 |