My Diplomarbeit (diploma thesis)

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 approximate the optimal solution.

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")