| EPSRC Reference: |
GR/S87454/01 |
| Title: |
Tractable Valued Consraints: An Algebraic Approach. |
| Principal Investigator: |
Jeavons, Professor PG |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
University of Oxford |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
20 June 2004 |
Ends: |
19 June 2006 |
Value (£): |
20,759
|
| EPSRC Research Topic Classifications: |
| Artificial Intelligence |
Fundamentals of Computing |
|
| EPSRC Industrial Sector Classifications: |
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
This proposal is a collaborative application involving Dr Peter Jeavons at the University of Oxford, Dr David Cohen at Royal Holloway, University of London, and Dr Martin Cooper at the University of Toulouse III, France. We are seeking funding to enable Dr Cooper to visit Dr Jeavons and Dr Cohen for 2 periods of 3 months in 2004 and 2005.Dr Cooper is a specialist in consistency techniques for the family of computational problems known as constraint satisfaction problems . This family of problems has been widely studied in computer science, and a number of tractable sub-cases of the constraint satisfaction problem have been identified using algebraic techniques. We have recently established that similar techniques can be devised to identify tractable cases of the more general valued constraint satisfaction problem . This is a very general framework which includes many standard forms of optimisation problem, so tractable classes for this problem are of interest for many practical optimisation problems. In this project we aim to obtain a complete description of all the tractable cases for some important special cases of the valued constraint satisfaction problem. We also aim to identify new tractable cases of the general problem and to develop a strong algebraic theory of the complexity of optimisation problems.
|
|
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.ox.ac.uk |