Approximation Algorithms - Detailseite

Many relevant computational problems are by nature not decision, but optimization problems; in the sense that one does not simply want a yes or no answer, but is interested in finding a best among a set of possible solutions. Famous examples of such problems are scheduling, facility location, or knapsack. Efficient computation of an optimum solution to such problems is often very difficult, usually testified by the NP-hardness of their underlying decision problem. This does however not exclude efficient computation of good solutions by so-called approximation algorithms.

This lecture is about the design and analysis of approximation algorithms. We will discuss standard methods like greedy, local search, cost scaling, etc. and how to generally assess the quality of approximations. Further, we will learn about special types of reductions to transfer approximation results between different optimization problems. Such reductions will also be used to show limitations of approximation algorithms.