Local search is better than random assignment for bounded occurrence Ordering k-CSPs

Konstantin Makarychev*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

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 + α(B, k)(Opt - Avg), where Opt is the value of the optimal solution; Avg is the expected value of the random solution; and α (B, k) = 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 Hastad [6], who recently showed that bounded occurrence 3-CSPs and monotone k-CSPs admit a non-trivial approximation.

Original languageEnglish (US)
Title of host publication30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013
Pages139-147
Number of pages9
DOIs
StatePublished - Dec 1 2013
Event30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013 - Kiel, Germany
Duration: Feb 27 2013Mar 2 2013

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume20
ISSN (Print)1868-8969

Other

Other30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013
CountryGermany
CityKiel
Period2/27/133/2/13

Keywords

  • Approximation algorithms
  • Approximation resistance
  • Ordering CSPs

ASJC Scopus subject areas

  • Software

Cite this

Makarychev, K. (2013). Local search is better than random assignment for bounded occurrence Ordering k-CSPs. In 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013 (pp. 139-147). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 20). https://doi.org/10.4230/LIPIcs.STACS.2013.139