License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2015.184
URN: urn:nbn:de:0030-drops-49135
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4913/
Bus, Norbert ;
Garg, Shashwat ;
Mustafa, Nabil H. ;
Ray, Saurabh
Improved Local Search for Geometric Hitting Set
Abstract
Over the past several decades there has been steady progress towards the goal of polynomial-time approximation schemes (PTAS) for fundamental geometric combinatorial optimization problems. A foremost example is the geometric hitting set problem: given a set P of points and a set D of geometric objects, compute the minimum-sized subset of P that hits all objects in D. For the case where D is a set of disks in the plane, a PTAS was finally achieved in 2010, with a surprisingly simple algorithm based on local-search. Since then, local-search has turned out to be a powerful algorithmic approach towards achieving good approximation ratios for geometric problems (for geometric independent-set problem, for dominating sets, for the terrain guarding problem and several others).
Unfortunately all these algorithms have the same limitation: local search is able to give a PTAS, but with large running times. That leaves open the question of whether a better understanding - both combinatorial and algorithmic - of local search and the problem can give a better approximation ratio in a more reasonable time. In this paper, we investigate this question for hitting sets for disks in the plane. We present tight approximation bounds for (3,2)-local search and give an (8+\epsilon)-approximation algorithm with expected running time ˜O(n^{2.34}); the previous-best result achieving a similar approximation ratio gave a 10-approximation in time O(n^{15}) -- that too just for unit disks. The techniques and ideas generalize to (4,3) local search. Furthermore, as mentioned earlier, local-search has been used for several other geometric optimization problems; for all these problems our results show that (3,2) local search gives an 8-approximation and no better \footnote{This is assuming the use of the standard framework. Improvement of the approximation factor by using additional properties specific to the problem may be possible.}. Similarly (4,3)-local search gives a 5-approximation for all these problems.
BibTeX - Entry
@InProceedings{bus_et_al:LIPIcs:2015:4913,
author = {Norbert Bus and Shashwat Garg and Nabil H. Mustafa and Saurabh Ray},
title = {{Improved Local Search for Geometric Hitting Set}},
booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
pages = {184--196},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-78-1},
ISSN = {1868-8969},
year = {2015},
volume = {30},
editor = {Ernst W. Mayr and Nicolas Ollinger},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/4913},
URN = {urn:nbn:de:0030-drops-49135},
doi = {10.4230/LIPIcs.STACS.2015.184},
annote = {Keywords: hitting sets, Delaunay triangulation, local search, disks, geometric algorithms}
}
|
Keywords: |
|
hitting sets, Delaunay triangulation, local search, disks, geometric algorithms |
|
Collection: |
|
32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) |
|
Issue Date: |
|
2015 |
|
Date of publication: |
|
26.02.2015 |
