AdONE Seminar: Prof. Andreas Wiese (TUM)

Approximation algorithms for packing problems

Many problems in combinatorial optimization are NP-hard, and thus we do not expect to find efficient (polynomial time) algorithms for them. However, often it is possible to find an efficient algorithm that computes a provably near-optimal solution, i.e., a solution whose quality differs from the optimum only by a bounded factor. Such an algorithm is called an approximation algorithm. In this talk, we will discuss approximation algorithms for packing problems, like the classical knapsack problem and generalizations of it. In particular, during the last years there has been significant advances on problems like the two-dimensional geometric knapsack problem and the unsplittable flow problem on a path. We will see these recent results, including the (currently best) (4/3+epsilon)-approximation algorithm for two-dimensional knapsack and the (1+epsilon)-approximation algorithm for unsplittable flow problem on a path.