Approximation algorithm for non-boolean MAX k-CSP

Konstantin Makarychev; Yury Makarychev

doi:10.1007/978-3-642-32512-0_22

Approximation algorithm for non-boolean MAX k-CSP

Konstantin Makarychev^*, Yury Makarychev

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

6 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 ₂ problem with a slightly improved approximation guarantee.

Original language	English (US)
Title of host publication	Approximation, Randomization, and Combinatorial Optimization
Subtitle of host publication	Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings
Pages	254-265
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-32512-0_22
State	Published - 2012
Event	15th 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 2012 → Aug 17 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7408 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012
Country/Territory	United States
City	Cambridge, MA
Period	8/15/12 → 8/17/12

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-32512-0_22

Cite this

Makarychev, K., & Makarychev, Y. (2012). Approximation algorithm for non-boolean MAX k-CSP. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings (pp. 254-265). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7408 LNCS). https://doi.org/10.1007/978-3-642-32512-0_22

Makarychev, Konstantin ; Makarychev, Yury. / Approximation algorithm for non-boolean MAX k-CSP. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings. 2012. pp. 254-265 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b503a8def7d44b2f8e19fca4a8bbfcf0,

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

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

author = "Konstantin Makarychev and Yury Makarychev",

year = "2012",

doi = "10.1007/978-3-642-32512-0_22",

language = "English (US)",

isbn = "9783642325113",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "254--265",

booktitle = "Approximation, Randomization, and Combinatorial Optimization",

note = "15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012 ; Conference date: 15-08-2012 Through 17-08-2012",

}

Makarychev, K & Makarychev, Y 2012, Approximation algorithm for non-boolean MAX k-CSP. in Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7408 LNCS, pp. 254-265, 15th 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, 8/15/12. https://doi.org/10.1007/978-3-642-32512-0_22

Approximation algorithm for non-boolean MAX k-CSP. / Makarychev, Konstantin; Makarychev, Yury.

Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings. 2012. p. 254-265 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7408 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Makarychev, Konstantin

AU - Makarychev, Yury

PY - 2012

Y1 - 2012

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

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

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

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

U2 - 10.1007/978-3-642-32512-0_22

DO - 10.1007/978-3-642-32512-0_22

M3 - Conference contribution

AN - SCOPUS:84865293289

SN - 9783642325113

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 254

EP - 265

BT - Approximation, Randomization, and Combinatorial Optimization

T2 - 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012

Y2 - 15 August 2012 through 17 August 2012

ER -

Makarychev K, Makarychev Y. Approximation algorithm for non-boolean MAX k-CSP. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings. 2012. p. 254-265. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-32512-0_22

Approximation algorithm for non-boolean MAX k-CSP

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this