|
| EPSRC Reference: |
GR/L09936/01 |
| Title: |
TRACTABILITY IN CONSTRAINT SATISFACTION PROBLEMS WITH APPLICATIONS TO FREQUENCY ASSIGNMENT |
| Principal Investigator: |
Professor PG Jeavons |
| Other Investigators: |
|
| Researcher Co-investigator: |
|
| Project Partner: |
|
| Department: |
Computer Science |
| Organisation: |
Royal Holloway, Univ of London |
| Scheme: |
Standard Research |
| Starts: |
01 October 1996 |
Ends: |
30 September 1998 |
Value (£): |
100,408
|
| EPSRC Research Topic Classifications: |
| Radio Frequency (RF) and Microwave Technology |
|
|
| EPSRC Industrial Sector Classifications: |
| Aerospace, Defence and Marine |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary |
Many important computational problems may be formulated as constraint satisfaction problems and this class of problems has been widely studied. The general form of this problem is intractable, but many results have identified sufficient conditions which lead to computationally tractability. This project aims to develop these results further, and to bridge the gap between the theoretical advances and practical applications. The project will therefore focus on a particular type of constraint satisfaction problem, known as the frequency assignment problem. This problem is of considerable commercial and strategic importance in the area of telecommunications, but has so far resisted attempts to find effective computational solutions. It therefore provides an ideal test-bed for the development of new algorithmic approaches based on structural features. The project will make use of software already developed by the investigators, and a wide variety of realistic problem data supplied by the collaborators. The results obtained will therefore be of immediate practical relevance as well as providing new theoretical insights.
|
| Final Report Summary |
|
No final report summary is available for this grant.
|
| Further Information: |
|
| Organisation Website: |
http://www.rhul.ac.uk |
|
|