My diploma thesis is about a very theoretical topic: Find out lower bounds for the approximability of NP-hard optimazation problems.
It is widely believed that P!=NP which basically means, that there is a (big) class of optimazation problems for which the optimal solution isn't efficiently computable.
For these problems a wide variety of techniques were developed
to get algorithms which find a solution which isn't "too far"
away from the optimal solution. This algorithms
The question is if there are (worst-case) lower bounds for the quality of the approximate solutions. (If the algorithms have a polynomial running time.)
In my diploma thesis I looked at problems which have a linear lower bound; in the case of a minimazation problem, this means you can devise for every approximation algorithm an instance of the problem where the optimal solution has quality Q and the algorithm won't be able to find an optimal solution of quality better than cQ, and there is an algorithm which finds a solution with quality c'Q, with c'>c. In other words it is possible to devise an algorithm which will find a solution which is guaranteed to be only a linear factor away from the optimal solution, but the linear factor can't be made arbitrarily small, which means a lower bound for the factor exists.
Download (as "ps.gz")