TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)Seminar: Approximation Algorithms

COGA 5-Wheel

Page Content

to Navigation

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.


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

Seminar Schedule
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


Quick Access

Schnellnavigation zur Seite über Nummerneingabe