When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2015.184
URN: urn:nbn:de:0030-drops-49135
URL: https://drops.dagstuhl.de/opus/volltexte/2015/4913/
 Go to the corresponding LIPIcs Volume Portal

### Improved Local Search for Geometric Hitting Set

 pdf-format:

### 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},