TY - GEN

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

AU - Makarychev, Konstantin

PY - 2013/12/1

Y1 - 2013/12/1

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Approximation resistance

KW - Ordering CSPs

UR - http://www.scopus.com/inward/record.url?scp=84892569286&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84892569286&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.STACS.2013.139

DO - 10.4230/LIPIcs.STACS.2013.139

M3 - Conference contribution

AN - SCOPUS:84892569286

SN - 9783939897507

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 139

EP - 147

BT - 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013

T2 - 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013

Y2 - 27 February 2013 through 2 March 2013

ER -