Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable

Konstantin Makarychev; Yury Makarychev; Yuan Zhou

doi:10.1109/FOCS.2015.64

Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable

Konstantin Makarychev, Yury Makarychev, Yuan Zhou

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Scopus citations

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 language	English (US)
Title of host publication	Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015
Publisher	IEEE Computer Society
Pages	975-993
Number of pages	19
Volume	2015-December
ISBN (Electronic)	9781467381918
DOIs	https://doi.org/10.1109/FOCS.2015.64
State	Published - Dec 11 2015
Event	56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015 - Berkeley, United States Duration: Oct 17 2015 → Oct 20 2015

Other

Other	56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015
Country/Territory	United States
City	Berkeley
Period	10/17/15 → 10/20/15

Keywords

advantage over random
combinatorial optimization
fixed-parameter tractability
ordering CSP

ASJC Scopus subject areas

General Computer Science

Access to Document

10.1109/FOCS.2015.64

Cite this

@inproceedings{eaaef0ab87de4a768dacb110a5d380b0,

title = "Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable",

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.",

keywords = "advantage over random, combinatorial optimization, fixed-parameter tractability, ordering CSP",

author = "Konstantin Makarychev and Yury Makarychev and Yuan Zhou",

year = "2015",

month = dec,

day = "11",

doi = "10.1109/FOCS.2015.64",

language = "English (US)",

volume = "2015-December",

pages = "975--993",

booktitle = "Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015",

publisher = "IEEE Computer Society",

address = "United States",

note = "56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015 ; Conference date: 17-10-2015 Through 20-10-2015",

}

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. vol. 2015-December, 7354438, IEEE Computer Society, pp. 975-993, 56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, United States, 10/17/15. https://doi.org/10.1109/FOCS.2015.64

Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable. / Makarychev, Konstantin; Makarychev, Yury; Zhou, Yuan.
Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015. Vol. 2015-December IEEE Computer Society, 2015. p. 975-993 7354438.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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

VL - 2015-December

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 -

Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable

Abstract

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this