Exact algorithms for NP-hard problems

点击翻译按钮获取中文摘要

We propose to study exact algorithms for NP-hard 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. NP-hard 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 NP-hard 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 NP-hard problems with respect to the (worst-case) 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 NP-hard problems we hope to find out whether thresholds for different problems are somehow related to each other.