TU Berlin

FG Kombinatorische Optimierung und GraphenalgorithmenSeminar: Approximationsalgorithmen

COGA 5-Wheel

Inhalt des Dokuments

zur Navigation

Seminar on approximation algorithms and related topics

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 and related topics. 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 or the course on Online Algorithms in WS 2014/15).

Important dates

A preparatory meeting where possible seminar topics etc. are presented will take place on April 15, 2015, 10:15 am, in room MA 517.

The first meeting will be on May 20, 2015, 10:00-12:00 am, in room MA 315. Every participant is expected to give a short 5-minutes introductory presentation of his/her topic.


The actual seminar talks (60 minutes each) will take place on

8th of July 2015 (Wednesday): room MA 313


10th of July 2015 (Friday): room MA 744

(from 9:00 to 18:00h)



Schnellnavigation zur Seite über Nummerneingabe