Page Content
There is no English translation for this web page.
Seminar: Approximation Algorithms
An approximation algorithm for an NP-hard optimization problem is a polynomial time algorithm that always finds a feasible solution whose value is provably close to the optimum solution value. More precisely, the value of the computed solution must be within a factor alpha of the optimum. alpha is the performance guarantee of the approximation algorithm.
The field of approximation algorithms is among the most active research areas of algorithmic discrete mathematics today. It combines a rich and deep mathematical theory with the promise of profound practical impact.
Prerequisites
The purpose of this seminar is to read and understand recent results from the literature on Approximation Algorithms. Participants are expected to have good knowledge of standard techniques and algorithms in the area of Approximation Algorithms (e.g. from the course on Approximation Algorithms in WS 2012/13).
Important Dates
A preparatory meeting where possible seminar topics etc. are presented will take place on February 13, 2013 after the Approximation Algorithms class (at 11:45h).
The seminar takes place tuesdays, 10-12 am, in room MA 545.
Seminar Schedule
| Date | Speaker | Paper |
|---|---|---|
| April 9, 2013 | Anne-Marie George | Better and Simpler Approximation Algorithms for the Stable Marriage Problem, Zoltán Király |
| April 16, 2013 | Laura Vargas Koch | Catch Them if You Can: How to Serve Impatient Users, Cygan, Englert, Gupta, Mucha, Sankowski |
| April 23, 2013 | Daniel Breitbach | Local Search for k-Median and Facility Location, chap. 9 in Shmoys & Williamson |
| April 30, 2013 | Isabel Beckenbach | Sampling and Cost-Sharing: Approximation Algorithms for Stochastic Optimization Problems, Gupta, Pal, Ravi, Sinha |
| May 7, 2013 | Hendrik Schrezenmaier | Constant Factor Approximation Algorithms for the Knapsack Median Problem, Amit Kumar |
| May 14, 2013 | Hongmei Zhao | Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching, Davanur, Jain, Kleinberg |
| May 21, 2013 | Christoph Stettin | Approximating k-Median via Preudo-Approximation, Shi Li & Ola Svensson |
| May 28, 2013 | ––– | ––– |
| June 4, 2013 | Gerald Bartz | A Simpler Proof for O(congestion + dilation) Packet Routing, Thomas Rothvoß |
| June 11, 2013 | Karl Däubel | A Linear Time Approximation Algorithm for Weighted Matchings in Graphs, Drake & Hougardy |
| June 18, 2013 | Tobias Buchwald | When LP is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings, Bansal, Gupta, Li, Mestre, Nagarajan, Rudra |
| June 25, 2013 | Benjamin Müller | An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem, Byrka & Aardal |
| July 2, 2013 | Andreas Wierz | Eight-Fifth Approximation for TSP-Path, András Sebo |