TY - GEN
T1 - Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable
AU - Makarychev, Konstantin
AU - Makarychev, Yury
AU - Zhou, Yuan
PY - 2015/12/11
Y1 - 2015/12/11
N2 - We study the satisfiability of ordering constraint satisfaction problems (CSPs) above average. We prove the conjecture of Gutin, van Iersel, Mnich, and Yeo that the satisfiability above average of ordering CSPs of arity k is fixed-parameter tractable for every k. Previously, this was only known for k=2 and k=3. We also generalize this result to more general classes of CSPs, including CSPs with predicates defined by linear equations. To obtain our results, we prove a new Bonami-type inequality for the Efron - Stein decomposition. The inequality applies to functions defined on arbitrary product probability spaces. In contrast to other variants of the Bonami Inequality, it does not depend on the mass of the smallest atom in the probability space. We believe that this inequality is of independent interest.
AB - We study the satisfiability of ordering constraint satisfaction problems (CSPs) above average. We prove the conjecture of Gutin, van Iersel, Mnich, and Yeo that the satisfiability above average of ordering CSPs of arity k is fixed-parameter tractable for every k. Previously, this was only known for k=2 and k=3. We also generalize this result to more general classes of CSPs, including CSPs with predicates defined by linear equations. To obtain our results, we prove a new Bonami-type inequality for the Efron - Stein decomposition. The inequality applies to functions defined on arbitrary product probability spaces. In contrast to other variants of the Bonami Inequality, it does not depend on the mass of the smallest atom in the probability space. We believe that this inequality is of independent interest.
KW - advantage over random
KW - combinatorial optimization
KW - fixed-parameter tractability
KW - ordering CSP
UR - http://www.scopus.com/inward/record.url?scp=84960358298&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84960358298&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2015.64
DO - 10.1109/FOCS.2015.64
M3 - Conference contribution
AN - SCOPUS:84960358298
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 975
EP - 993
BT - Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015
PB - IEEE Computer Society
T2 - 56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015
Y2 - 17 October 2015 through 20 October 2015
ER -