Near-optimal algorithms for unique games

Moses Charikar*, Konstantin Makarychev, Yury Makarychev

*Corresponding author for this work

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

86 Scopus citations

Abstract

Unique games are constraint satisfaction problems that can be viewed as a generalization of Max-Cut to a larger domain size. The Unique Games Conjecture states that it is hard to distinguish between instances of unique games where almost all constraints are satisfiable and those where almost none are satisfiable. It has been shown to imply a number of inapproximability results for fundamental problems that seem difficult to obtain by more standard complexity assumptions. Thus, proving or refuting this conjecture is an important goal. We present significantly improved approximation algorithms for unique games. For instances with domain size k where the optimal solution satisfies 1 - ε fraction of all constraints, our algorithms satisfy roughly k/2-ε) and 1 - O(√ε log k) fraction of all constraints. Our algorithms are based on rounding a natural semidefinite programming relaxation for the problem and their performance almost matches the integrality gap of this relaxation. Our results are near optimal if the Unique Games Conjecture is true, i.e. any improvement (beyond low order terms) would refute the conjecture.

Original languageEnglish (US)
Title of host publicationSTOC'06
Subtitle of host publicationProceedings of the 38th Annual ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Pages205-214
Number of pages10
ISBN (Print)1595931341, 9781595931344
DOIs
StatePublished - 2006
Event38th Annual ACM Symposium on Theory of Computing, STOC'06 - Seattle, WA, United States
Duration: May 21 2006May 23 2006

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume2006
ISSN (Print)0737-8017

Other

Other38th Annual ACM Symposium on Theory of Computing, STOC'06
Country/TerritoryUnited States
CitySeattle, WA
Period5/21/065/23/06

Keywords

  • Approximation Algorithms
  • Constraint Satisfaction Problems
  • Semidefinite Programming
  • Unique Games

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Near-optimal algorithms for unique games'. Together they form a unique fingerprint.

Cite this