|
| EPSRC Reference: |
GR/R81213/01 |
| Title: |
Tractable Valued Constraints:: An Initial Study |
| Principal Investigator: |
Professor D Cohen |
| Other Investigators: |
|
| Researcher Co-investigator: |
|
| Project Partner: |
|
| Department: |
Computer Science |
| Organisation: |
Royal Holloway, Univ of London |
| Scheme: |
Standard Research |
| Starts: |
05 July 2002 |
Ends: |
04 October 2002 |
Value (£): |
5,638
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
|
|
| EPSRC Industrial Sector Classifications: |
|
| Related Grants: |
|
| Panel History: |
|
|
Summary |
This proposal is for a Visiting Fellowship for a period of 3 months to enable Dr Martin Cooper of the University of Toulouse III, France, to work with Dr Peter Jeavons at the University of Oxford and with Dr David Cohen at Royal Holloway. 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 believe that it may be possible to use similar techniques 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 would be of interest for many practical optimisation problems. In this short initial study we hope to demonstrate that interesting tractable cases exist for the valued constraint satisfaction problem, and hence establish a novel research programme on this topic.
|
| Final Report Summary |
This proposal is for a Visiting Fellowship for a period of 3 months to enable Dr Martin Cooper of the University of Toulouse III, France, to work with Dr Peter Jeavons at the University of Oxford and with Dr David Cohen at Royal Holloway. 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 believe that it may be possible to use similar techniques 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 would be of interest for many practical optimisation problems. In this short initial study we hope to demonstrate that interesting tractable cases exist for the valued constraint satisfaction problem, and hence establish a novel research programme on this topic.
|
| Further Information: |
|
| Organisation Website: |
http://www.rhul.ac.uk |
|
|