Approximation algorithm for non-boolean MAX k-CSP

Konstantin Makarychev*, Yury Makarychev

*Corresponding author for this work

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

5 Scopus citations

Abstract

In this paper, we present a randomized polynomial-time approximation algorithm for MAX k-CSP d. In MAX k-CSP d, we are given a set of predicates of arity k over an alphabet of size d. Our goal is to find an assignment that maximizes the number of satisfied constraints. Our algorithm has approximation factor Ω(kd/d k) (when k ≥ Ω(log d)). This bound is asymptotically optimal assuming the Unique Games Conjecture. The best previously known algorithm has approximation factor Ω(k log d/d k). We also give an approximation algorithm for the boolean MAX k-CSP 2 problem with a slightly improved approximation 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
Pages254-265
Number of pages12
DOIs
StatePublished - Aug 28 2012
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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Approximation algorithm for non-boolean MAX k-CSP'. Together they form a unique fingerprint.

Cite this