Guarding 1.5D Terrains with Demands
| Autor: | Domagoj Ševerdija, Khaled Elbassioni, Domagoj Matijevic |
|---|---|
| Přispěvatelé: | Jan Vahrenhold |
| Jazyk: | angličtina |
| Rok vydání: | 2012 |
| Předmět: |
Mathematical optimization
Applied Mathematics Approximation algorithm Terrain Computer Science::Computational Geometry čuvanje 1.5D terena LP relaksacija zahtjevi Computer Science Applications Linear programming relaxation Set (abstract data type) Cardinality Computational Theory and Mathematics Decomposition (computer science) Point (geometry) 1.5D terrain guarding LP relaxation totally balanced matrices demands approximation algorithm Mathematics Integer (computer science) |
| Popis: | 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, i.e a $5/2(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 dictated by the linear programming relaxation of the corresponding covering problem. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|