1 Search Results for "Bus, Norbert"

Document

DOI: 10.4230/LIPIcs.STACS.2015.184

Improved Local Search for Geometric Hitting Set

Authors: Norbert Bus, Shashwat Garg, Nabil H. Mustafa, and Saurabh Ray

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

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.

Cite as

Norbert Bus, Shashwat Garg, Nabil H. Mustafa, and Saurabh Ray. Improved Local Search for Geometric Hitting Set. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 184-196, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{bus_et_al:LIPIcs.STACS.2015.184,
  author =	{Bus, Norbert and Garg, Shashwat and Mustafa, Nabil H. and Ray, Saurabh},
  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 =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.184},
  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}
}

Refine by Author
1 Bus, Norbert
1 Garg, Shashwat
1 Mustafa, Nabil H.
1 Ray, Saurabh

Refine by Classification

Refine by Keyword
1 Delaunay triangulation
1 disks
1 geometric algorithms
1 hitting sets
1 local search

Refine by Type
1 document

Refine by Publication Year
1 2015

1 Search Results for "Bus, Norbert"

Improved Local Search for Geometric Hitting Set

Abstract

Cite as

Thanks for your feedback!

Could not send message