License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2013.139
URN: urn:nbn:de:0030-drops-39290
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/3929/
Go to the corresponding LIPIcs Volume Portal

Makarychev, Konstantin

Local Search is Better than Random Assignment for Bounded Occurrence Ordering k-CSPs

pdf-format:
17.pdf (0.6 MB)

Abstract

We prove that the Bounded Occurrence Ordering k-CSP Problem is not approximation resistant. We give a very simple local search algorithm that always performs better than the random assignment algorithm (unless, the number of satisfied constraints does not depend on the ordering). Specifically, the expected value of the solution returned by the algorithm is at least ALG >= AVG + alpha(B,k)(OPT-AVG), where OPT is the value of the optimal solution; AVG is the expected value of the random solution; and alpha(B,k) = Omega_k(B^{-(k+O(1))}) is a parameter depending only on k (the arity of the CSP) and B (the maximum number of times each variable is used in constraints).

The question whether bounded occurrence ordering k-CSPs are approximation resistant was raised by Guruswami and Zhou (2012), who recently showed that bounded occurrence 3-CSPs and "monotone" k-CSPs admit a non-trivial approximation.

BibTeX - Entry

@InProceedings{makarychev:LIPIcs:2013:3929,
  author =	{Konstantin Makarychev},
  title =	{{Local Search is Better than Random Assignment for Bounded Occurrence Ordering k-CSPs}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{139--147},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Natacha Portier and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/3929},
  URN =		{urn:nbn:de:0030-drops-39290},
  doi =		{10.4230/LIPIcs.STACS.2013.139},
  annote =	{Keywords: approximation algorithms, approximation resistance, ordering CSPs}
}

Keywords: approximation algorithms, approximation resistance, ordering CSPs
Collection: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Issue Date: 2013
Date of publication: 26.02.2013

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