TY - GEN
T1 - Near-optimal algorithms for maximum constraint satisfaction problems
AU - Charikar, Moses
AU - Makarychev, Konstantin
AU - Makarychev, Yury
N1 - Funding Information:
http://www.cs.princeton.edu/~moses/ Supported by NSF ITR grant CCR-0205594, NSF CAREER award CCR-0237113, MSPA-MCS award 0528414, and an Alfred P. Sloan Fellowship. http://www.cs.princeton.edu/~kmakaryc/ Supported by a Gordon Wu fellowship. http://www.cs.princeton.edu/~ymakaryc/ Supported by a Gordon Wu fellowship.
Publisher Copyright:
Copyright © 2007 by the Association for Computing Machinery, Inc. and the Society for Industrial and Applied Mathematics.
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84969264045&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84969264045&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84969264045
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 62
EP - 68
BT - Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007
PB - Association for Computing Machinery
T2 - 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007
Y2 - 7 January 2007 through 9 January 2007
ER -