An LP-designed algorithm for constraint satisfaction
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 M...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Published: |
2006
|
| Summary: | 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. |
|---|