EPSRC logo

Details of Grant 

EPSRC Reference: GR/L09844/01
Title: TRACTABILITY IN CONSTRAINT SATISFACTION PROBLEMS WITH APPLICATIONS TO FREQUENCY ASSIGNMENT
Principal Investigator: Smith, Professor DH
Other Investigators:
Hurley, Professor S
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