| EPSRC Reference: |
EP/C543831/1 |
| Title: |
Constraint Satisfaction Problems: Complexity and Approximability |
| Principal Investigator: |
Krokhin, Professor A |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
Durham, University of |
| Scheme: |
Advanced Fellowship (Pre-FEC) |
| Starts: |
01 September 2005 |
Ends: |
31 August 2010 |
Value (£): |
298,802
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
Logic & Combinatorics |
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
| Panel Date | Panel Name | Outcome |
|
22 Mar 2005
|
EURYI Central Panel
|
Deferred
|
|
13 Apr 2005
|
ICT Fellowships 2005 Interview Panel
|
Deferred
|
|
11 Mar 2005
|
ICT Fellowships Sift Panel 2005
|
Deferred
|
|
|
Summary on Grant Application Form |
|
The proposed research concerns constraint satisfaction problems (CSPs) and their natural optimisation version, maximum constraint satisfaction problems (Max CSPs). 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. In Max CSP, the goal is to satisfy as many constraints as possible. This general setting allows one to express, in a natural way, a wide variety of problems encountered in Artificial Intelligence, Combinatorial Optimisation, Graph Theory, Logic Programming, Database Theory and elsewhere.The two main directions of research in CSP are as follows: one is Al-oriented and comprises modelling other problems as CSPs, empirical studies and constraint programming, while the other is Theoretical Computer Science-oriented and studies the structure and the complexity of fragments of CSP and its many variants. In this proposal, we follow the second direction.Solving constraint satisfaction and optimisation problems 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 the complexity and approximability of constraint satisfaction and optimisation better (lower) than the general case, the ultimate goal being a complete classification of complexity of these problems. Due to the many ways in which constraint satisfaction problems can be viewed, many methods can be used to evaluate the complexity of constraint satisfaction problems. We plan to combine methods from algebra, logic and combinatorics in our research.
|
|
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: |
|