Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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. ISBN 3-540-21236-1. ISSN 0302-9743.

Full text not available from this repository, contact author.

Request Changes to record.

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
Official Date: 2004
Dates:
DateEvent
2004UNSPECIFIED
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

Data sourced from Thomson Reuters' Web of Knowledge

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: publications@live.warwick.ac.uk
Contact Details
About Us