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