An LP-designed algorithm for constraint satisfaction

Conference item

The class Max (r, 2)-CSP consists of constraint satisfaction problems with at most two r-valued variables per clause. For instances with n variables and m binary clauses, we present an (O) over tilde (r(19m/100))-time algorithm. It is the fastest algorithm for most problems in the class (including Max Cut and Max 2-Sat), and in combination with "Generalized CSPs" introduced in a companion paper, also allows counting, sampling; and the solution of problems like Max Bisection that escape the usual CSP framework. Linear programming is key to the design as well as the analysis of the algorithm.

Authors: Scott, A; Sorkin, G

• Publication status: Published
• Journal: ALGORITHMS - ESA 2006, PROCEEDINGS
• Volume: 4168
• Pages: 588-599
• Publication date: 2006-01-01
• Event title: 14th Annual European Symposium on Algorithms (ESA 2006)
• EISSN: 1611-3349
• ISSN: 0302-9743
• ISBN: 3540388753
• Keywords: MAX-CUT; TIME