### 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 language | English (US) |
---|---|

Title of host publication | Approximation, Randomization, and Combinatorial Optimization |

Subtitle of host publication | Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings |

Pages | 158-169 |

Number of pages | 12 |

DOIs | |

State | Published - Aug 28 2012 |

Externally published | Yes |

Event | 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 Duration: Aug 15 2012 → Aug 17 2012 |

### Publication series

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

Volume | 7408 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012 |
---|---|

Country | United States |

City | Cambridge, MA |

Period | 8/15/12 → 8/17/12 |

### Fingerprint

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

### Cite this

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

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

*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

}

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 -