Uni-Logo
Algorithms and Complexity
 

Vorlesung
"Combinatorial Optimization"
Sommersemester 2008
Prof. Dr. Susanne Albers
Dr. Alexander Souza


Vorlesung

Die folgenden Formalitäten bilden den Rahmen der Veranstaltung: 3 + 1 SWS

Vorlesung

  • Zeit: Mittwochs 11:00-13:00 und Freitags 11:00-13:00 Uhr (2-wöchig, biweekly)
  • Ort: SR 01-018 Geb. 101

Übung

  • Zeit: Freitags 11:00-13:00 (2-wöchig, biweekly)
  • Ort: SR 01-018 Geb. 101

Leistungsnachweis

Individuelle, 30-minütige mündliche Prüfung.

Kreditpunkte

In dieser Veranstaltung können 6 ECTS-Punkte erworben werden. Anmeldung über LSF-HIS.
Bei Anregungen und Fragen wenden Sie sich bitte an Alexander Souza.

Aktuelles / News

Deutsch English
26.4.2008:
Die vorgeholte Vorlesung findet am Montag 28.4.08 im Raum 101-02-016/018 von 9-11 ct statt. The lecture to be preponed will take place on Monday 28.4.08 Room 101-02-016/018 at 9-11 ct
6.5.2008:
Übungen finden alle zwei Wochen statt. Die erste Übung ist am Freitag 23.5.08.
 The exercises will take place biweekly. The first one will be on friday 23.5.08.
30.5.2008:
Eine vorläufige Version von Kapitel 3 ist verfügbar.
 A preliminary version of chapter 3 is available.
13.6.2008:
Eine vorläufige Version von Kapitel 4 ist verfügbar.
 A preliminary version of chapter 4 is available.
9.7.2008:
Eine vorläufige Version der Kapitel 5 und 6 ist verfügbar.
 A preliminary version of chapters 5 and 6 is available.
23.7.2008:
Eine vollständige (aber noch nicht nochmals gegengelesene) Version des Skripts ist verfügbar.
 A complete (but not yet proof-read) version of the lecture notes is available.
15.8.2008:
Die mündlichen Prüfungen sind für 12.9.2008 oder 19.9.2008 angesetzt. Bitte per mail für einen Termin anmelden.
Die Prüfung findet im Gebäude 079 Raum 00 009 (von Prof. Albers) statt.
 The oral exams are scheduled for 12.9.2008 or 19.9.2008. Please register for a slot per mail.
The exam takes place in building 079 room 00 009 (of Prof. Albers).
12.9.2008
Zeit/TimeName
10:00 - 10:30 Cameron Smith
10:40 - 11:10 Huawei Miao
11:20 - 11:50 Sebastian Schefczyk
12:00 - 12:30 Steffen Schmidt
13:30 - 14:00 Torsten Böttcher
14:10 - 14:40 Iftikhar Ahmad
14:50 - 15:20
15:30 - 16:00
19.9.2008
Zeit/TimeName
10:00 - 10:30 Janine Kühn
10:40 - 11:10
11:20 - 11:50
12:00 - 12:30
13:30 - 14:00
14:10 - 14:40
14:50 - 15:20
15:30 - 16:00

Inhalt der Veranstaltung

Die Vorlesung wird je nach Auditorium auf Deutsch oder Englisch gehalten. Es wird weiterführender Stoff zu Algorithmentheorie behandelt. Dieser eignet sich sehr gut als Vorbereitung für eine Diplom- bzw Semesterarbeit in dem Bereich.

The lecture will be given in german or english depending on the audience. Advanced material of algorithm theory will be treated. The lecture is an excellent preparation for a thesis in this area.

Preliminary Table of Contents:

  1. Introduction
    • Examples
    • Combinatorial Optimization Problems
    • Algorithms and Approximation
    • Basic Graph Theory
  2. Linear Programming
    • Linear Programs
    • Polyhedra
    • Simplex Algorithm
    • Duality
  3. Network Flows
    • Max-Flow Min-Cut Theorem
    • Edmonds-Karp Algorithm
    • Min-Cost Flows
    • Assignment Problem
  4. Knapsack Problem
    • Fractional Knapsack
    • Greedy Algorithm
    • FPTAS
  5. Set Cover
    • Greedy Algorithm
    • Randomized Rounding
    • Primal-Dual Algorithm
  6. Satisfiability
    • Randomized Algorithm
    • Derandomization
  7. Network Design
    • Steiner Tree
    • Facility Location

Für eine erfolgreiche Teilnahme an der Vorlesung sind grundlegende Kenntnisse in den Bereichen Algorithmen, Optimierung und Wahrscheinlichkeitsrechnung hilfreich aber nicht Voraussetzung.

Exercise Sheets

Assignments to be handed in at the lecture. You will get the corrected assignments back at the exercise sessions.

Exercise SheetReturn Date
121. 5. 2008
24. 6. 2008
318. 6. 2008
42. 7. 2008
516. 7. 2008

Lecture Notes

Available when ready. Please mail typos and other errors you find.

ChaptersVersion
1-723.7.2008 (complete but not proof-read version)

Slides

The slides presented during the lectures can be downloaded here.

SlidesVersion
Linear Programs28. 4. 2008
Simplex Algorithm8. 5. 2008 (corrected)
Simplex Example8. 5. 2008
Ford-Fulkerson Algorithm3. 6. 2008
Ford-Fulkerson Animation3. 6. 2008
Edmonds-Karp Algorithm3. 6. 2008
Knapsack Greedy Algorithm12. 6. 2008
Dynamic Programming Knapsack12. 6. 2008
Knapsack FPTAS Algorithm12. 6. 2008
Set Cover Greedy Algorithm17. 6. 2008
Primal Dual Set Cover Algorithm2. 7. 2008
Simple Rounding Set Cover Algorithm2. 7. 2008
Randomized Rounding Set Cover Algorithm2. 7. 2008

Weiterführendes Material

Hier finden Sie Links zu Materialien, die in der sonstigen Literatur nicht oder nicht ausführlich genug behandelt werden.
  • Wird begleitend bekannt gegeben.

Literatur

Die folgenden Literaturangaben dienen als Grundlage für die Vorlesung.