| EPSRC Reference: |
GR/L09936/01 |
| Title: |
TRACTABILITY IN CONSTRAINT SATISFACTION PROBLEMS WITH APPLICATIONS TO FREQUENCY ASSIGNMENT |
| Principal Investigator: |
Jeavons, Professor PG |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
Royal Holloway, Univ of London |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
01 October 1996 |
Ends: |
30 September 1998 |
Value (£): |
100,408
|
| EPSRC Research Topic Classifications: |
| RF & Microwave Technology |
|
|
| EPSRC Industrial Sector Classifications: |
| Aerospace, Defence and Marine |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
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.
|
|
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: |
|