Near-optimal algorithms for maximum constraint satisfaction problems

Moses Charikar*, Konstantin Makarychev, Yury Makarychev

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

38 Scopus citations

Abstract

In this article, we present two approximation algorithms for the maximum constraint satisfaction problem with k variables in each constraint (MAX k-CSP). Given a (1 - ε) satisfiable 2CSP our first algorithm finds an assignment of variables satisfying a 1 - O(ε) fraction of all constraints. The best previously known result, due to Zwick, was 1 - O(ε1/3). The second algorithm finds a ck/2k approximation for the MAX k-CSP problem (where c > 0.44 is an absolute constant). This result improves the previously best known algorithm by Hast, which had an approximation guarantee of (k/(2k log k)). Both results are optimal assuming the unique games conjecture and are based on rounding natural semidefinite programming relaxations. We also believe that our algorithms and their analysis are simpler than those previously known.

Original languageEnglish (US)
Article number32
JournalACM Transactions on Algorithms
Volume5
Issue number3
DOIs
StatePublished - Jul 1 2009

Keywords

  • MAX 2CSP
  • MAX k-CSP
  • SDP

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

Fingerprint

Dive into the research topics of 'Near-optimal algorithms for maximum constraint satisfaction problems'. Together they form a unique fingerprint.

Cite this