| EPSRC Reference: |
GR/T05325/01 |
| Title: |
Complexity of Constraint Optimisation on ordered Domains: An initial Study |
| Principal Investigator: |
Krokhin, Professor A |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
University of Warwick |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
22 June 2004 |
Ends: |
21 July 2004 |
Value (£): |
3,170
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
|
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
The constraint satisfaction problem (CSP) is a well-known formalism in Al and computer science. The aim in a constraint satisfaction problem is to find an assignment of values to a given set of variables, subject to constraints on the values which can be assigned to certain specified subsets of variables. This general setting allows one to express, in a natural way, a wide variety of problems encountered in Artificial Intelligence, Combinatorial Optimisation, Algebra, Graph Theory, Logic Programming, Database Theory and elsewhere. A natural optimisation version of CSP is the maximum constraint satisfaction problem (Max CSP) where the goal is to maximise the number of satisfied constraints.Solving CSP and Max CSP in full generality is difficult, and it is very unlikely that general efficient algorithms for these problems exist. We propose to study which restrictions on the type of constraints make Max CSP tractable. It was shown recently that the algebraic condition of supermodularity on a suitably ordered domain is relevant in the study of complexity of Max CSP. We plan to investigate the extent to which this approach is applicable to Max CSP and to clarify the role of ordering of the domain in this application.
|
|
Key Findings |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Potential use in non-academic contexts |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| Date Materialised |
|
|
|
|
Sectors submitted by the Researcher |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
| Project URL: |
|
| Further Information: |
|
| Organisation Website: |
http://www.warwick.ac.uk |