The Library
Identifying efficiently solvable cases of Max CSP
Tools
Tools
Tools
UNSPECIFIED (2004) Identifying efficiently solvable cases of Max CSP. In: 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, FRANCE, APR, 2004. Published in: STACS 2004, PROCEEDINGS, 2996 pp. 152-163.
Full text not available from this repository.Abstract
In this paper we study the complexity of the maximum constraint satisfaction problem (Max CSP) over an arbitrary finite domain. We describe a novel connection between this problem and the supermodular function maximization problem (which is dual to the submodular function minimization problem). Using this connection, we are able to identify large classes of efficiently solvable subproblems of Max CSP arising from certain restrictions on the constraint types. Until now, the only known polynomial-time solvable cases for this form of optimization problem were restricted to constraints over a 2-valued (Boolean) domain. Here we obtain the first examples of general families of efficiently solvable cases of Max CSP for arbitrary finite domains, by considering supermodular functions on finite lattices. Finally, we show that the equality constraint over a non-Boolean domain is non-supermodular, and, when combined with some simple unary constraints, gives rise to cases of Max CSP which are hard even to approximate.
| Item Type: | Conference Item (UNSPECIFIED) |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
| Series Name: | LECTURE NOTES IN COMPUTER SCIENCE |
| Journal or Publication Title: | STACS 2004, PROCEEDINGS |
| Publisher: | SPRINGER-VERLAG BERLIN |
| ISBN: | 3-540-21236-1 |
| ISSN: | 0302-9743 |
| Editor: | Diekert, V and Habib, M |
| Date: | 2004 |
| Volume: | 2996 |
| Number of Pages: | 12 |
| Page Range: | pp. 152-163 |
| Publication Status: | Published |
| Title of Event: | 21st Annual Symposium on Theoretical Aspects of Computer Science |
| Location of Event: | Montpellier, FRANCE |
| Date(s) of Event: | APR, 2004 |
| URI: | http://wrap.warwick.ac.uk/id/eprint/8428 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
