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 polynomialtime 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 minimumsized 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 localsearch. Since then, localsearch has turned out to be a powerful algorithmic approach towards achieving good approximation ratios for geometric problems (for geometric independentset 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 previousbest result achieving a similar approximation ratio gave a 10approximation 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, localsearch has been used for several other geometric optimization problems; for all these problems our results show that (3,2) local search gives an 8approximation 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 5approximation 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 = {184196},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897781},
ISSN = {18688969},
year = {2015},
volume = {30},
editor = {Ernst W. Mayr and Nicolas Ollinger},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/4913},
URN = {urn:nbn:de:0030drops49135},
doi = {10.4230/LIPIcs.STACS.2015.184},
annote = {Keywords: hitting sets, Delaunay triangulation, local search, disks, geometric algorithms}
}
2015
Keywords: 

hitting sets, Delaunay triangulation, local search, disks, geometric algorithms 
Seminar: 

32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Issue date: 

2015 
Date of publication: 

2015 