|
|
 |
LS 2 HomeTeaching
(German)  Winter
04/05Sommer 04Diplomarbeiten (pdf)Frühere
SemesterService Travel Staff Contact PrivateExternal Links Universität DortmundComputer Science FacultyResearch Center 531Research Center 475Research Cluster 1126Student Advisory
|
Sommersemester 2005
Vorlesung ApproximationsalgorithmenDozent: Piotr KrystaTermine: Mo. 14:15-15:45 Uhr, GB 4, 318 Mi. 14.15-15:45 Uhr, HG 1, HS 2 <>Beginn: 11. April 2005 Gegenstand der VorlesungThis will be a self-contained course on approximation algorithms, with an emphasis on basic ideas and principles. The course will be given in English, but the lecturing style will be interactive enough so that the students could fully follow and understand the material. It will cover most of the material contained in the popular book on "`Approximation Algorithms"' by Vijay Vazirani, and possibly some topics from the book "`Approximation Algorithms for NP-hard Problems"' edited by Dorit Hochbaum. We will start from simple problems and simple approximation algorithms for these problems, and as the course will proceed we will advance to more sophisticated approximation techniques. For many of the considered problems, we will try to find their aplicability to some real-life situations, coming, e.g., from the Internet. A preliminary (and not complete) list of topics is as follows. The first list contains problems for which we will use simple, combinatorial approaches: Set Cover, Steiner Tree, Traveling Salesman problem (TSP). Multiway Cut, k-Cut, k-Center problems. Knapsack packing problem, Bin packing problem. Minimum Makespan Scheduling. Now, we list problems for which we will develop more advanced, LP-based techniques: Set Cover, Maximum Satisfiability, Scheduling on Unrelated Parallel Machines. Steiner Forest problem, Steiner Network (Survivable Network Design). Facility Location, k-Median problems, Semidefinite Programming. We will also cover some extra topics not included in these books, for example, combinatorial greedy approximation algorithms for hard integer packing problems motivated by practical applications in Electronic Commerce (e.g., in Combinatorial Auctions). In this context, we will discuss connections between such algorithms and algorithmic mechanism design -- a very recent exciting area with applications to Electronic Commerce and the Internet. Literature: Book: "Approximation Algorithms" by Vijay Vazirani. Book: "Approximation Algorithms for NP-hard Problems" edited by Dorit Hochbaum. Some original research papers that has appeared recently. Additionally, I will point you to some lecture notes (Skript) available on the Internet. |