Computational Complexity - Bachelor's and Master's Theses
Oliver Putz: Approximation Algorithms for the Multi-criteria MAX TSP Problem
Bachelor's Thesis, 2007.
Advisor: Prof. Dr. Markus Bläser
In this thesis we will study a modified version of a well known problemin computer science: The travelling salesperson problem or the problem of finding a Hamiltonian cycle of maximal or minimal weight in a complete graph. While the classic TSP problem is defined on a graph with a weight function that maps edges to real-valued weights, we will have a look at what happens if we use weight functions that assign vectorial weights to edges. This in fact is a very natural extension to the classical TSP problem as we normally always need to consider several objectives when trying to find an optimal solution to some problem. The real world salesperson for example might not just want to find a shortest route connecting all the cities, but might also want to minimize the travel time, the amount of gas used and the toll to be paid for using highways. This example already shows one of the main problems that may arise: There might be no solution that is optimal in all objectives. Using a toll road might be the fastest way to travel but using it will increase the travel cost due to the toll to be paid. Another instance of such a multi-criteria optimization problem is to build a car that uses little gas, has a powerful engine, has all the latest technical features, and is reasonably priced. As there might be mutually contradictory objectives to optimize for when trying to find solutions to these kinds of problems, we will introduce and use the notion of pareto-optimal solutions.
As with the classic Hamiltonian cycle problem where we can try to find a Hamiltonian cycle of maximal or minimal weight, we also can split the multi-criteria version of the problem along the same lines. In this thesis we will solely consider the case where we are to find a Hamiltonian cycle of maximal weight. Algorithms for finding Hamiltonian cycles of minimal weight are discussed for example by Manthey and Ram (2007).
As we know that the classic Hamiltonian cycle problem with a real-valued weight function already is NP hard, we cannot hope to find exact solutions to the multi-criteria Hamiltonian cycle problem in polynomial time either. Therefore, we will focus on finding approximative solutions to the problem. We will develop an algorithm that finds a set of solutions such that we approximate each possible solution of the TSP problem with a factor of at least 1/4 if we optimize for two objectives.
At the end of this thesis we furthermore will give an outlook about what happens if we try to optimize according to more than just two objectives.
Approximating Multi-Criteria Max-TSP.
European Symposium on Algorithms (ESA) in Lecture Notes in Computer Science 5193:185-197. Springer, 2008.