Back to Search
Start Over
Guarding 1.5D terrains with demands.
- Source :
-
International Journal of Computer Mathematics . Nov2012, Vol. 89 Issue 16, p2143-2151. 9p. - Publication Year :
- 2012
-
Abstract
- In this paper, we consider the 1.5D terrain guarding problem in which every point on the terrain that is to be covered has an integer demand associated with it. The goal is to find a minimum cardinality set of guards such that each point is guarded by a number of guards satisfying its demand. We present a first constant-factor approximation algorithm for the problem, that is, a (1+1/d min)-approximation algorithm, where d min is a minimum demand. The algorithm is based on solving appropriate subproblems established by a decomposition of the main problem due to linear programming relaxation of the corresponding covering problem. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00207160
- Volume :
- 89
- Issue :
- 16
- Database :
- Academic Search Index
- Journal :
- International Journal of Computer Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 83568937
- Full Text :
- https://doi.org/10.1080/00207160.2012.707800