Inhalt des Dokuments
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.
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 ).
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.
|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,
2013||Hendrik Schrezenmaier||Constant Factor
Approximation Algorithms for the Knapsack Median Problem, Amit
2013||Hongmei Zhao||Randomized Primal-Dual
Analysis of RANKING for Online Bipartite Matching, Davanur, Jain,
k-Median via Preudo-Approximation, Shi Li & Ola
|June 4, 2013||Gerald
Bartz||A Simpler Proof for O(congestion + dilation) Packet
Routing, Thomas Rothvoß|
2013||Karl Däubel||A Linear Time
Approximation Algorithm for Weighted Matchings in Graphs, Drake &
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 &
2013||Andreas Wierz||Eight-Fifth Approximation for TSP-Path, András