Book chapter
An Approximation Scheme for Terrain Guarding
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp.140-148
Lecture Notes in Computer Science, Springer Berlin Heidelberg
2009
DOI: 10.1007/978-3-642-03685-9_11
Abstract
We obtain a polynomial time approximation scheme for the terrain guarding problem improving upon several recent constant factor approximations. Our algorithm is a local search algorithm inspired by the recent results of Chan and Har-Peled [2] and Mustafa and Ray [15]. Our key contribution is to show the existence of a planar graph that appropriately relates the local and global optimum.
Details
- Title: Subtitle
- An Approximation Scheme for Terrain Guarding
- Creators
- Matt Gibson - University of IowaGaurav Kanade - University of IowaErik Krohn - University of IowaKasturi Varadarajan - University of Iowa
- Resource Type
- Book chapter
- Publication Details
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp.140-148
- Publisher
- Springer Berlin Heidelberg; Berlin, Heidelberg
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/978-3-642-03685-9_11
- eISSN
- 1611-3349
- ISSN
- 0302-9743
- Language
- English
- Date published
- 2009
- Academic Unit
- Computer Science
- Record Identifier
- 9984259427502771
Metrics
7 Record Views