| EPSRC Reference: |
GR/L09844/01 |
| Title: |
TRACTABILITY IN CONSTRAINT SATISFACTION PROBLEMS WITH APPLICATIONS TO FREQUENCY ASSIGNMENT |
| Principal Investigator: |
Smith, Professor DH |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
School of Accounting & Maths |
| Organisation: |
University of Glamorgan |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
30 September 1996 |
Ends: |
29 December 1998 |
Value (£): |
64,830
|
| 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. The general form of this problem is intractable, but many results have identified sufficient conditions which lead to 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 will be of immediate practical relevance and provide 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: |
http://www.glam.ac.uk |