English English

Termine

Art
Termin / Ort
Beginn
Veranstalter
V4
Do. 13:30h - 15:00h / AH III
Fr. 10:30h - 12:00h / AH III
14.04.2005
Vöcking, Fischer, Röglin

 

Inhalt

Die Vorlesung gibt einen Überblick über klassische Optimierungsverfahren. Dieser Überblick wird ergänzt um neuartige probabilistische Analysen und spieltheoretische Aspekte, die den Schwerpunkten unserer aktuellen Forschung auf diesem Gebiet entsprechen.

  1. Nicht-ganzzahlige Optimierung - Simplexverfahren - Ellipsoidmethode - Primal-Duale Algorithmen
  2. Ganzzahlige Optimierung - Heuristiken - Greedy Methode - Dynamische Programmierung
  3. Probabilistische Analysen
  4. Analyse spieltheoretischer Gleichgewichte
  5. Randomisierte & Approximative Optimierungsmethoden
  6. Mechanism Design - Multi-Unit Auktionen - Kombinatorische Auktionen - Cost Sharing

Material

  • Optimierung
    • Teil 1: Einführung in die lineare Programmierung, Skript: [PS] [PDF]
    • Teil 2: Heuristiken zur Optimierung, Skript: [PS] [PDF]
    • Teil 3: Probalistische Analysen von Algorithmen
      • Folien zur Einführungsvorlesung am 27. Mai: [PDF]
      • Typical Properties of Winners and Losers in Discrete Optimization, Rene Beier und Berthold Vöcking (STOC 2004): [PDF] [PS]
  • Spieltheorie
    • Teil 1: Einführung in die Spieltheorie
      • Skript: Einführung in die Spieltheorie [PS] [PDF]
      • Skript: Evolutionary Game Theory (Nicht Prüfungsrelevant.) [PS] [PDF]
    • Teil 2: Selfish Routing
      • How bad is selfish routing? Tim Roughgarden und Eva Tardos (Journal of the ACM, 49(2):236-259, März 2002) [PS] [PDF]
        (Prüfungsrelevant sind die Kapitel 1 bis 3)
      • Lecture Notes: Selfish Routing - a Simple, Discrete Model [PS] [PDF]
      • Lecture Notes: Lecture Notes on Congestion Games [PDF]
    • Teil 3: Mechanism Design
      • Lecture Notes: Utilitarian Mechanism Design [PDF]
      • Lecture Notes: Cost Sharing Mechanisms [PDF]

 

Kontakt

Heiko Röglin: roeglin (at) cs.rwth-aachen.de