EPSRC Reference: 
EP/D053633/1 
Title: 
Exact algorithms for NPhard problems 
Principal Investigator: 
Paulusma, Professor D 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Computer Science 
Organisation: 
Durham, University of 
Scheme: 
First Grant Scheme PreFEC 
Starts: 
12 September 2006 
Ends: 
11 March 2010 
Value (£): 
93,337

EPSRC Research Topic Classifications: 
Fundamentals of Computing 
Logic & Combinatorics 

EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 

Summary on Grant Application Form 
We propose to study exact algorithms for NPhard problems. An algorithm can be seen as a set of constructions for solving a problem. An exact algorithm is an algorithm that solves a problem to optimality. NPhard problems are a special kind of optimization problems for which most probably no polynomial time (i.e. fast ) algorithm exists. As an example of an NPhard problem we can consider the travelling salesman problem (TSP). In this problem a travelling salesman has to make a tour through a number of cities starting and returning to city 1 in such a way that the total travel distance is minimal. Of course, it is possible to solve this problem to optimality by computing the distance of every tour and then choosing a tour with minimum distance. This simple algorithm costs a huge amount of computation time. Already in the case of a relatively small number of cities, the problem can not be solved (within reasonable time) on any modern computer that uses this algorithm.Our research will result in faster algorithms for this kind of problems. Even a faster exact algorithm that does not run in polynomial time can already mean that in practice much larger instances (cf. with many cities in TSP) can be solved. Secondly, we hope that our research will lead to a better understanding of NPhard problems with respect to the (worstcase) time it takes to solve them. Since it is very unlikely to obtain polynomial time algorithms for this kind of problems, we can not expect to develop exact algorithms that are faster than a certain threshold. By developing faster algorithms for a number of NPhard problems we hope to find out whether thresholds for different problems are somehow related to each other.

Key Findings 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Potential use in nonacademic 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: 
