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.SoCG.2018.48
URN: urn:nbn:de:0030-drops-87615
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8761/
Go to the corresponding LIPIcs Volume Portal

Jartoux, Bruno ; Mustafa, Nabil H.

Optimality of Geometric Local Search

pdf-format:
LIPIcs-SoCG-2018-48.pdf (0.5 MB)

Abstract

Up until a decade ago, the algorithmic status of several basic çlass{NP}-complete problems in geometric combinatorial optimisation was unresolved. This included the existence of polynomial-time approximation schemes (PTASs) for hitting set, set cover, dominating set, independent set, and other problems for some basic geometric objects. These past nine years have seen the resolution of all these problems--interestingly, with the same algorithm: local search. In fact, it was shown that for many of these problems, local search with radius lambda gives a (1+O(lambda^{-1/2}))-approximation with running time n^{O(lambda)}. Setting lambda = Theta(epsilon^{-2}) yields a PTAS with a running time of n^{O(epsilon^{-2})}.
On the other hand, hardness results suggest that there do not exist PTASs for these problems with running time poly(n) * f(epsilon) for any arbitrary f. Thus the main question left open in previous work is in improving the exponent of n to o(epsilon^{-2}).
We show that in fact the approximation guarantee of local search cannot be improved for any of these problems. The key ingredient, of independent interest, is a new lower bound on locally expanding planar graphs, which is then used to show the impossibility results. Our construction extends to other graph families with small separators.

BibTeX - Entry

@InProceedings{jartoux_et_al:LIPIcs:2018:8761,
  author =	{Bruno Jartoux and Nabil H. Mustafa},
  title =	{{Optimality of Geometric Local Search}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{48:1--48:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Bettina Speckmann and Csaba D. T{\'o}th},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8761},
  URN =		{urn:nbn:de:0030-drops-87615},
  doi =		{10.4230/LIPIcs.SoCG.2018.48},
  annote =	{Keywords: local search, expansion, matchings, Hall's marriage theorem}
}

Keywords: local search, expansion, matchings, Hall's marriage theorem
Collection: 34th International Symposium on Computational Geometry (SoCG 2018)
Issue Date: 2018
Date of publication: 08.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI