| EPSRC Reference: |
GR/L24014/01 |
| Title: |
CONSTRAINEDNESS OF COMPUTATIONAL PROBLEMS |
| Principal Investigator: |
Prosser, Dr P |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer and Information Sciences |
| Organisation: |
University of Strathclyde |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
01 October 1996 |
Ends: |
30 September 1999 |
Value (£): |
170,499
|
| EPSRC Research Topic Classifications: |
|
| EPSRC Industrial Sector Classifications: |
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
Many computational problems involve search. For example, we may need to search for the best time-table for staff in a school or hospital. It is often worth investing a great amount of effort in solving such problems as an optimal or near-optimal solution can be of considerable economic value. The hardest computational problems tend to occur where problems are neither obviously under- constrained nor obviously over- constrained. We have recently proposed a definition of the constrainedness of computational problems. This project has two aims. First, can this definition of constrainedness predict the location of hard computational problems in a wide variety of domains? Second, can we improve the performance of algorithms as a consequence? For example, given a choice of representations for a problem, do we prefer the least or most constrained? This project is both very novel and timely, unifying work performed in isolation in several different domains. It will result in better algorithms and heuristics for a wide variety of problems. In addition, it will greatly improve our knowledge about what makes computational problems hard. The applicants are at the cutting edge of research in this area. The area itself is attracting significant attention internationally.
|
|
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.strath.ac.uk |