Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable

Konstantin Makarychev, Yury Makarychev, Yuan Zhou

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

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015
PublisherIEEE Computer Society
Pages975-993
Number of pages19
ISBN (Electronic)9781467381918
DOIs
StatePublished - Dec 11 2015
Externally publishedYes
Event56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015 - Berkeley, United States
Duration: Oct 17 2015Oct 20 2015

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2015-December
ISSN (Print)0272-5428

Other

Other56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015
CountryUnited States
CityBerkeley
Period10/17/1510/20/15

    Fingerprint

Keywords

  • advantage over random
  • combinatorial optimization
  • fixed-parameter tractability
  • ordering CSP

ASJC Scopus subject areas

  • Computer Science(all)

Cite this

Makarychev, K., Makarychev, Y., & Zhou, Y. (2015). Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable. In Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015 (pp. 975-993). [7354438] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2015-December). IEEE Computer Society. https://doi.org/10.1109/FOCS.2015.64