Springe zum Hauptinhalt

Lehre

Logo der Arbeitsgruppe

Diskrete Optimierung (M03)

Sommersemester 2010

Vorlesung: C. Helmberg

Prof. Christoph Helmberg

Vorlesung:

Montag 13:45-15:20, Raum 2/N002
Donnerstag, 7:30-9:05, Raum 2/N005 (nur 22.4: 2/NK004)


Kurzbeschreibung

Inhalt:

Optimierung über diskreten Grundmengen, Theorie und praktische Verfahren der linearen Optimierung mit Ganzzahligkeitsbedingungen, Relaxationen und duale Probleme, Lagrangerelaxation und Dekomposition, ganzzahlige Kegel und Polyeder, polynomial lösbare Probleme, ganzzahlige min-max-Resultate, Schnittebenenverfahren, semidefinite Relaxation, Approximationsalgorithmen.

Auf Wunsch in Englisch.

Zielgruppe:

wob. : D_MaIn6, D_Ma_6, D_WM_6, M_MaDI2, M_MaOW2, M_MaSF2, M_Fi_2, D_InEM6, D_InEM8, M_In_2, M_In_4, M_MaNT2

Vorwissen:

Grundlagen der Optimierung, Grundlegende Begriffe der Graphentheorie

Folien zur Einführung in die Vorlesung

Literatur

  • Cook, W. J., Cunningham, W.H., Pulleyblank, W. R., Schrijver, A.; Combinatorial Optimization; Wiley 1998

  • Groetschel, M., Lovasz, L., Schrijver, A.; Geometric Algorithms and Combinatorial Optimization, Springer 1988

  • Korte, B. und Vygen, J.; Combinatorial Optimization, Springer 2000

  • Wolsey, L. A.; Integer Programming; Wiley 1998

  • Schrijver, A.; Theory of Linear and Integer Programming; Wiley 1986

  • Schrijver, A.; Combinatorial Optimization; Springer 2003