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
|
| _version_ | 1826294941385490432 |
|---|---|
| author | Scott, A Sorkin, G |
| author_facet | Scott, A Sorkin, G |
| author_sort | Scott, A |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T03:53:27Z |
| format | Conference item |
| id | oxford-uuid:c210e70d-d1e6-4f93-9cfd-b7dda1f6ffb9 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T03:53:27Z |
| publishDate | 2006 |
| record_format | dspace |
| spelling | oxford-uuid:c210e70d-d1e6-4f93-9cfd-b7dda1f6ffb92022-03-27T06:06:13ZAn LP-designed algorithm for constraint satisfactionConference itemhttp://purl.org/coar/resource_type/c_5794uuid:c210e70d-d1e6-4f93-9cfd-b7dda1f6ffb9Symplectic Elements at Oxford2006Scott, ASorkin, GThe 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. |
| spellingShingle | Scott, A Sorkin, G An LP-designed algorithm for constraint satisfaction |
| title | An LP-designed algorithm for constraint satisfaction |
| title_full | An LP-designed algorithm for constraint satisfaction |
| title_fullStr | An LP-designed algorithm for constraint satisfaction |
| title_full_unstemmed | An LP-designed algorithm for constraint satisfaction |
| title_short | An LP-designed algorithm for constraint satisfaction |
| title_sort | lp designed algorithm for constraint satisfaction |
| work_keys_str_mv | AT scotta anlpdesignedalgorithmforconstraintsatisfaction AT sorking anlpdesignedalgorithmforconstraintsatisfaction AT scotta lpdesignedalgorithmforconstraintsatisfaction AT sorking lpdesignedalgorithmforconstraintsatisfaction |