Conference icon

Conference

An LP-designed algorithm for constraint satisfaction

Abstract:

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 us...

Expand abstract
Publication status:
Published

Actions


Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Mathematical Inst
Role:
Author
Volume:
4168
Pages:
588-599
Publication date:
2006-01-01
EISSN:
1611-3349
ISSN:
0302-9743
URN:
uuid:c210e70d-d1e6-4f93-9cfd-b7dda1f6ffb9
Source identifiers:
23719
Local pid:
pubs:23719
ISBN:
3-540-38875-3
Keywords:

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP