Approximating bounded occurrence ordering CSPs

Venkatesan Guruswami, Yuan Zhou

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

Abstract

A theorem of Håstad shows that for every constraint satisfaction problem (CSP) over a fixed size domain, instances where each variable appears in at most O(1) constraints admit a non-trivial approximation algorithm, in the sense that one can beat (by an additive constant) the approximation ratio achieved by the naive algorithm that simply picks a random assignment. We consider the analogous question for ordering CSPs, where the goal is to find a linear ordering of the variables to maximize the number of satisfied constraints, each of which stipulates some restriction on the local order of the involved variables. It was shown recently that without the bounded occurrence restriction, for every ordering CSP it is Unique Games-hard to beat the naive random ordering algorithm. In this work, we prove that the CSP with monotone ordering constraints xi 1 < xi 2<⋯< xi k of arbitrary arity k can be approximated beyond the random ordering threshold 1/k! on bounded occurrence instances. We prove a similar result for all ordering CSPs, with arbitrary payoff functions, whose constraints have arity at most 3. Our method is based on working with a carefully defined Boolean CSP that serves as a proxy for the ordering CSP. One of the main technical ingredients is to establish that certain Fourier coefficients of this proxy constraint have substantial mass. These are then used to guarantee a good ordering via an algorithm that finds a good Boolean assignment to the variables of a low-degree bounded occurrence multilinear polynomial. Our algorithm for the latter task is similar to Håstad's earlier method but is based on a greedy choice that achieves a better performance guarantee.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings
Pages158-169
Number of pages12
DOIs
StatePublished - Aug 28 2012
Externally publishedYes
Event15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012 - Cambridge, MA, United States
Duration: Aug 15 2012Aug 17 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7408 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012
CountryUnited States
CityCambridge, MA
Period8/15/128/17/12

Fingerprint

Constraint satisfaction problems
Constraint Satisfaction Problem
Beat
Assignment
Restriction
Linear Ordering
Performance Guarantee
Arbitrary
Approximation algorithms
Fourier coefficients
Approximation Algorithms
Monotone
Maximise
Polynomials
Game
Polynomial
Approximation
Theorem

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Guruswami, V., & Zhou, Y. (2012). Approximating bounded occurrence ordering CSPs. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings (pp. 158-169). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7408 LNCS). https://doi.org/10.1007/978-3-642-32512-0_14

Approximating bounded occurrence ordering CSPs. / Guruswami, Venkatesan; Zhou, Yuan.

Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings. 2012. p. 158-169 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7408 LNCS).

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

Guruswami, V & Zhou, Y 2012, Approximating bounded occurrence ordering CSPs. in Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7408 LNCS, pp. 158-169, 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012, Cambridge, MA, United States, 8/15/12. https://doi.org/10.1007/978-3-642-32512-0_14
Guruswami V, Zhou Y. Approximating bounded occurrence ordering CSPs. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings. 2012. p. 158-169. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-32512-0_14
Guruswami, Venkatesan ; Zhou, Yuan. / Approximating bounded occurrence ordering CSPs. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings. 2012. pp. 158-169 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{0208dd12928c42a7a59115b468011f92,
title = "Approximating bounded occurrence ordering CSPs",
abstract = "A theorem of H{\aa}stad shows that for every constraint satisfaction problem (CSP) over a fixed size domain, instances where each variable appears in at most O(1) constraints admit a non-trivial approximation algorithm, in the sense that one can beat (by an additive constant) the approximation ratio achieved by the naive algorithm that simply picks a random assignment. We consider the analogous question for ordering CSPs, where the goal is to find a linear ordering of the variables to maximize the number of satisfied constraints, each of which stipulates some restriction on the local order of the involved variables. It was shown recently that without the bounded occurrence restriction, for every ordering CSP it is Unique Games-hard to beat the naive random ordering algorithm. In this work, we prove that the CSP with monotone ordering constraints xi 1 < xi 2<⋯< xi k of arbitrary arity k can be approximated beyond the random ordering threshold 1/k! on bounded occurrence instances. We prove a similar result for all ordering CSPs, with arbitrary payoff functions, whose constraints have arity at most 3. Our method is based on working with a carefully defined Boolean CSP that serves as a proxy for the ordering CSP. One of the main technical ingredients is to establish that certain Fourier coefficients of this proxy constraint have substantial mass. These are then used to guarantee a good ordering via an algorithm that finds a good Boolean assignment to the variables of a low-degree bounded occurrence multilinear polynomial. Our algorithm for the latter task is similar to H{\aa}stad's earlier method but is based on a greedy choice that achieves a better performance guarantee.",
author = "Venkatesan Guruswami and Yuan Zhou",
year = "2012",
month = "8",
day = "28",
doi = "10.1007/978-3-642-32512-0_14",
language = "English (US)",
isbn = "9783642325113",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "158--169",
booktitle = "Approximation, Randomization, and Combinatorial Optimization",

}

TY - GEN

T1 - Approximating bounded occurrence ordering CSPs

AU - Guruswami, Venkatesan

AU - Zhou, Yuan

PY - 2012/8/28

Y1 - 2012/8/28

N2 - A theorem of Håstad shows that for every constraint satisfaction problem (CSP) over a fixed size domain, instances where each variable appears in at most O(1) constraints admit a non-trivial approximation algorithm, in the sense that one can beat (by an additive constant) the approximation ratio achieved by the naive algorithm that simply picks a random assignment. We consider the analogous question for ordering CSPs, where the goal is to find a linear ordering of the variables to maximize the number of satisfied constraints, each of which stipulates some restriction on the local order of the involved variables. It was shown recently that without the bounded occurrence restriction, for every ordering CSP it is Unique Games-hard to beat the naive random ordering algorithm. In this work, we prove that the CSP with monotone ordering constraints xi 1 < xi 2<⋯< xi k of arbitrary arity k can be approximated beyond the random ordering threshold 1/k! on bounded occurrence instances. We prove a similar result for all ordering CSPs, with arbitrary payoff functions, whose constraints have arity at most 3. Our method is based on working with a carefully defined Boolean CSP that serves as a proxy for the ordering CSP. One of the main technical ingredients is to establish that certain Fourier coefficients of this proxy constraint have substantial mass. These are then used to guarantee a good ordering via an algorithm that finds a good Boolean assignment to the variables of a low-degree bounded occurrence multilinear polynomial. Our algorithm for the latter task is similar to Håstad's earlier method but is based on a greedy choice that achieves a better performance guarantee.

AB - A theorem of Håstad shows that for every constraint satisfaction problem (CSP) over a fixed size domain, instances where each variable appears in at most O(1) constraints admit a non-trivial approximation algorithm, in the sense that one can beat (by an additive constant) the approximation ratio achieved by the naive algorithm that simply picks a random assignment. We consider the analogous question for ordering CSPs, where the goal is to find a linear ordering of the variables to maximize the number of satisfied constraints, each of which stipulates some restriction on the local order of the involved variables. It was shown recently that without the bounded occurrence restriction, for every ordering CSP it is Unique Games-hard to beat the naive random ordering algorithm. In this work, we prove that the CSP with monotone ordering constraints xi 1 < xi 2<⋯< xi k of arbitrary arity k can be approximated beyond the random ordering threshold 1/k! on bounded occurrence instances. We prove a similar result for all ordering CSPs, with arbitrary payoff functions, whose constraints have arity at most 3. Our method is based on working with a carefully defined Boolean CSP that serves as a proxy for the ordering CSP. One of the main technical ingredients is to establish that certain Fourier coefficients of this proxy constraint have substantial mass. These are then used to guarantee a good ordering via an algorithm that finds a good Boolean assignment to the variables of a low-degree bounded occurrence multilinear polynomial. Our algorithm for the latter task is similar to Håstad's earlier method but is based on a greedy choice that achieves a better performance guarantee.

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

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

U2 - 10.1007/978-3-642-32512-0_14

DO - 10.1007/978-3-642-32512-0_14

M3 - Conference contribution

AN - SCOPUS:84865306896

SN - 9783642325113

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 158

EP - 169

BT - Approximation, Randomization, and Combinatorial Optimization

ER -