| EPSRC Reference: |
GR/M53370/01 |
| Title: |
RANDOMIZED AND PROBABILISTIC METHODS IN ALGORITHM DESIGN |
| Principal Investigator: |
Dyer, Professor ME |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Sch of Computing |
| Organisation: |
University of Leeds |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
01 February 1999 |
Ends: |
31 July 1999 |
Value (£): |
28,280
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
|
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
The research is in the theoretical area of computer science and its applications. It will have two main components. The first is in the Markov chain Monte Carlo method. Here it is hoped to provide new positive and negative results for problems of practical and theoretical interest, for example the problem of counting independent sets in graphs of degree 5, which has applications to statistical physics.The second component will be in the probabilistic analysis of algorithms and approximate algorithms for hard problems. Frieze has great experience in these areas. Particular problems to be addressed will include searching for an expected polynomial time algorithm for the 0-1 knapsack problem under the model in which all coefficients are selected independently from the unit internal. This builds on earlier work of Dyer and Frieze. In the area of approximation algorithms, an attempt to build on the framework of Frieze and Kannan for solving dense problems will be undertaken.
|
|
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.leeds.ac.uk |