Approximation algorithm for non-boolean Max-k-CSP

Konstantin Makarychev, Yury Makarychev

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

In this paper we present a randomized polynomial-time approximation algorithm for MAX-k-CSPd. In MAX-k-CSPd 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=dk) (when k ≥ Ω(logd)). The best previously known algorithm has approximation factor Ω(k logd=dk). Our bound is asymptotically optimal when d = Ω(d). We also give an approximation algorithm for the Boolean MAX-k-CSP2 problem with a slightly improved approximation guarantee.

Original languageEnglish (US)
Pages (from-to)341-358
Number of pages18
JournalTheory of Computing
Volume10
DOIs
StatePublished - Oct 10 2014

Keywords

  • Approximation algorithm
  • Constraint satisfaction
  • Semidefinite programming

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics

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

Cite this