About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
ACM Transactions on Algorithms
Paper
Near-optimal algorithms for maximum constraint satisfaction problems
Abstract
In this article, we present two 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. © 2009 ACM.