Wintersemester 2009/2010
Prof. Dr. Manfred Kunde

[Mitteilungen] [Inhalte] [Termine] [Scheinerhalt] [Literatur] [Materialien]

Mitteilungen

Inhalte

1. Grundlagen der Approximation
   
   
2. Approximation mit absoluter Gütegarantie
1. Konzepte
2. Knotenfärbung
3. Schwierigkeit der Approximation des Rucksackproblems
   
   
3. Approximation mit relativer Gütegarantie
• Konzepte
• Traveling Salesperson
• Knotenfärbungen und Independent Set
  
  
4. Approximationsschemata
• Pseudopolynomielle Algorithmen
• Strenge Approximationsschemata
• Unmöglichkeitsergebnisse für Approximationsschemata
  
  
5. Techniken zur Approximation
   

Termine

• Vorlesung (Prof. Dr. M. Kunde)
• Montag, 13:00-14:30 Uhr, Sr HU 211/212
  
  
• Übung (S. Grau)
• Mittwoch (U), 13:00-14:30, Sr HU 012
  

Kriterien für den Scheinerhalt

Die Details werden noch bekannt gegeben.

Literatur und Links

• Rolf Wanka: Approximationsalgorithmen - Eine Einführung
  Leitfäden der Informatik, B.G. Teubner Verlag, 2006
  ISBN-10 3-519-00444-5
  ISBN-13 978-3-519-00444-8
  

Materialien und Übungsblätter

Dokumente zur Vorlesung

• Folie: Übungskriterien
• Folien zur Vorlesung vom 12.10.2009
• Folien zur Vorlesung vom 19.10.2009
• Folien zur Vorlesung vom 26.10.2009
• Folien zur Vorlesung vom 02.11.2009
• Folien zur Vorlesung vom 09.11.2009
• Folien zur Vorlesung vom 16.11.2009
• Folien zur Vorlesung vom 23.11.2009
• Folien zur Vorlesung vom 30.11.2009
• Folien zur Vorlesung vom 07.12.2009
• Folien zur Vorlesung vom 14.12.2009
• Folien zur Vorlesung vom 17.12.2009
• Folien zur Vorlesung vom 11.01.2010
• Folien zur Vorlesung vom 18.01.2010
• Folien zur Vorlesung vom 25.01.2010
• Folien zur Vorlesung vom 01.02.2010

Übungsblätter

• Übungsblatt 1
• Übungsblatt 2
• Übungsblatt 3
• Übungsblatt 4
• Übungsblatt 5
• Übungsblatt 6
• Übungsblatt 7
• Übungsblatt 8