Homepage for the Course Approximation Algorithms, E2002
Description of the course can be found in kursusbasen
News
The exam will be on January 6th 2003 instead of January 17th.
Pensumliste (ps,pdf).
Teacher
Inge Li Gørtz (inge@it-c.dk)
Where and When Fridays 9.15-13.00 in room 1.03. The course
consists of lectures and exercises.
Literature
Approximation Algorithms by Vijay
V. Vazirani. ISBN 3-540-65367-8. ©Springer-Verlag 2001.
A
Unified Approach to Approximation Algorithms for Bottleneck Problems by
Dorit S. Hochbaum amd David B. Shmoys. Journal of the ACM, Vol. 33, No. 3,
July 1986.
Introduction to Algorithms (Second edition) by Cormen,
Leierson, Rivest, and Stein. ISBN 0-262-53196-8. ©MIT Press 2001.
"Lecture Notes on Approximation Algorithms, Fall 1998" by
David P. Williamson.
IBM Research Report RC 21409, February 1999.
A Greedy Facility Location Algorithm Analyzed using Dual Fitting
by M. Mahdian, E. Markakis, A. Saber, and V. Vazirani.
In Proceedings of 5th International Workshop on Randomization and
Approximation Techniques in Computer Science,
vol 2129 of Lecture Notes in Computer Science, 2001.
A New Greedy Approach for Facility Location Problems
by K. Jain, M. Mahdian, and A. Saberi. STOC 2002.
Local Search Algorithms for Facility Location Problems by
Inge Li Gørtz. Lecture notes, Fall 2002.
Assignments
Assigment 1 (ps,pdf)
due September 30th.
Assigment 2 (ps,pdf)
due October 25th.
Solutions to Exercises
Week 1 (ps,pdf)
Lecture Plan
| Week | Date | Topic | Material |
| 1 (ps,pdf)
|
30/8 | Introduction | [VV 1.0,1.1,2.0,2.1]
|
| 2 (ps,pdf)
| 6/9 | Steiner tree, TSP, Multiway Cut, k-Cut
|
[VV 3,4] |
| 3 (ps,pdf)
| 13/9 | k-center, bottleneck problems |
[VV 5], [HS86].
|
| 4 | 20/9 | Facility location, k-median, local search
| Notes
|
| 5 (ps,pdf)
| 30/9 | LP rounding | [VV 14],[CLR 29]
|
| 6 (ps,pdf)
| 4/10 | LP duality | [VV 12]
|
| 7 (ps,pdf)
| 11/10 | LP primal-dual | [VV 15,24]
|
| . | 18/10 | Efterårsferie | .
|
| 8 | 25/10 | Cancelled | .
|
| 9 (ps,pdf)
|
1/11 |
Dual Fitting | [VV 13],[JMS02],[MMSV01]
|
| 10 (ps,pdf)
| 8/11 |
Knapsack, Bin Packing | [VV 8,9]
|
| 11 (ps,pdf)
| 15/11 | Multiway Cut | [VV 19]
|
| 12 | 22/11 | . | .
|
|
/Kurser E2002
/Approximations Algorithms
