Near-optimal algorithms for maximum constraint satisfaction problems

Moses Charikar, Konstantin Makarychev, Yury Makarychev

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

23 Scopus citations

Abstract

In this paper we present 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)
Title of host publicationProceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007
PublisherAssociation for Computing Machinery
Pages62-68
Number of pages7
ISBN (Electronic)9780898716245
StatePublished - 2007
Event18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 - New Orleans, United States
Duration: Jan 7 2007Jan 9 2007

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume07-09-January-2007

Other

Other18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007
CountryUnited States
CityNew Orleans
Period1/7/071/9/07

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

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

Cite this