Approximation algorithm for non-boolean Max-k-CSP

Konstantin Makarychev; Yury Makarychev

doi:10.4086/toc.2014.v010a013

Approximation algorithm for non-boolean Max-k-CSP

Konstantin Makarychev, Yury Makarychev

Computer Science

Research output: Contribution to journal › Article › peer-review

9 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 ≥ Ω(logd)). The best previously known algorithm has approximation factor Ω(k logd=d^k). Our bound is asymptotically optimal when d = Ω(d). We also give an approximation algorithm for the Boolean MAX-k-CSP₂ problem with a slightly improved approximation guarantee.

Original language	English (US)
Pages (from-to)	341-358
Number of pages	18
Journal	Theory of Computing
Volume	10
DOIs	https://doi.org/10.4086/toc.2014.v010a013
State	Published - Oct 10 2014

Funding

∗Supported by NSF CAREER award CCF-1150062 and NSF award IIS-1302662.

Keywords

Approximation algorithm
Constraint satisfaction
Semidefinite programming

ASJC Scopus subject areas

Theoretical Computer Science
Computational Theory and Mathematics

Access to Document

10.4086/toc.2014.v010a013

Cite this

@article{c7ed3f50a59445f5b49102e313985d67,

title = "Approximation algorithm for non-boolean Max-k-CSP",

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.",

keywords = "Approximation algorithm, Constraint satisfaction, Semidefinite programming",

author = "Konstantin Makarychev and Yury Makarychev",

note = "Funding Information: ∗Supported by NSF CAREER award CCF-1150062 and NSF award IIS-1302662. Publisher Copyright: {\textcopyright} 2014 Konstantin Makarychev and Yury Makarychev.",

year = "2014",

month = oct,

day = "10",

doi = "10.4086/toc.2014.v010a013",

language = "English (US)",

volume = "10",

pages = "341--358",

journal = "Theory of Computing",

issn = "1557-2862",

publisher = "University of Chicago, Department of Computer Science",

}

TY - JOUR

T1 - Approximation algorithm for non-boolean Max-k-CSP

AU - Makarychev, Konstantin

AU - Makarychev, Yury

PY - 2014/10/10

Y1 - 2014/10/10

N2 - 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.

AB - 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.

KW - Approximation algorithm

KW - Constraint satisfaction

KW - Semidefinite programming

UR - http://www.scopus.com/inward/record.url?scp=84963573715&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84963573715&partnerID=8YFLogxK

U2 - 10.4086/toc.2014.v010a013

DO - 10.4086/toc.2014.v010a013

M3 - Article

AN - SCOPUS:84963573715

SN - 1557-2862

VL - 10

SP - 341

EP - 358

JO - Theory of Computing

JF - Theory of Computing

ER -

Approximation algorithm for non-boolean Max-k-CSP

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this