|
|
Approximation: Theorie und Algorithmen (SS 2006)
 | News:
|
 | Lecturers:
Prof. Angelika
Steger
Prof. Emo Welzl
Prof. Peter Widmayer
|
| Assistant:
Patrick Traxler
|
| Where and When:
Wednesday, 10.00 - 12.00 Uhr, CAB H 56 (Lecture) und 12.00 - 13.00 Uhr,
CAB H 56 (Exercises)
|
| Language:
German, unless someone expresses preference for English
|
| Contents:
Many optimization problems are known to be NP-hard. Complexity theory
thus implies that, unless P=NP, we will not be able to design efficient
algorithms for these problems. Nevertheless we are often required to find
some kind of (good) algorithm. Here approximation algorithms are often a
good compromise. They combine efficiency with guarantees on the performance
ratio. The aim of this lecture is to provide an introduction into the theory
of approximation algorithms and open up the path to several up-to-date
research topics that can be the start for independent research on the
subject (in a bachelor/master/doctoral thesis).
|
| Prerequisites:
We assume familiarity with fundamental notions from
algorithms and complexity as they are taught within the first two years of a
Bachelor in Computer Science or Mathematics.
|
| Exam:
Oral exam (15 minutes) on 7. July. Please, send an e-mail to Prof. Steger if you are intending to do the exam.
|
| Schedule:
| Date |
Lecturer |
Topics |
Literature/Notes |
| 5. April |
Prof. Steger |
Introduction:
2-approximation for metric TSP,
non-approximability for general TSP,
2-approximation for Vertex Cover |
Ch. 1, script by Prof. Blaeser;
Ch. 1 & 3, Approximation Algorithms (V. V. Vazirani) |
| Complexity Classes for Optimization |
| 12. April |
Prof. Steger |
Definitions of optimization problems, approximization algorithms,
and the complexity classes PO, FPTAS, PTAS, APX, NPO;
non existence of FPTASs |
Ch. 7.3, The Steiner Tree Problem
(H.-J. Prömel, A. Steger) |
| 19. April |
Prof. Widmayer |
FPTAS - Knapsack:
dynamic programming, pseudopolynomial algorithms |
Ch. 8, Approximation Algorithms (V. V. Vazirani) |
| 26. April |
Prof. Steger |
PTAS - Bin Packing:
First Fit, First Fit Decreasing
asymptotic PTAS for Bin Packing,
PTAS for Balanced Bin Packing |
Ch. 9, Approximation Algorithms (V. V. Vazirani) |
| 3. May |
Prof. Steger |
APX:
Metric TSP (Christofides algorithm), Mininum Steiner Tree,
Maximum Exact 3SAT |
Ch. 3, Approximation Algorithms (V. V. Vazirani) |
| 10. May |
Prof. Widmayer |
non APX - Set Cover:
(ln(n)+1)-approximation algorithm, examples |
Ch. 2, Approximation Algorithms (V. V. Vazirani) |
| Lower Bounds |
| 17. May |
Prof. Steger |
Gap preserving reductions and APX-completeness |
slides |
| 24. May |
Prof. Steger |
PCPs |
slides |
| Highlights |
| 31. May |
Prof. Steger |
Approximating chromatic number; spanners |
slides |
| 7. June |
Prof. Steger |
PTAS for TSP in weighted planar graphs |
|
| 14. June |
Prof. Steger |
no lecture |
|
| 21. June |
Prof. Steger |
PTAS for Euclidean TSP |
slides |
| 28. June |
Prof. Welzl |
LP-Relaxation I |
|
| 5. July |
Prof. Welzl |
LP-Relaxation II |
|
| | Exercises:
| | Literature:
|
| Links:
|
|
