Zur

Seminar: Kombinatorische Optimierung

 Zur Seite des Instituts für Mathematik
 

Sommersemester 2008

  
LV-Nr.: 0230 L 318

 
Dr. Ralf Borndörfer (www)    und     Prof. Dr. Martin Grötschel (www)
 

Aktuelles (down)   Inhalt (down)   Voraussetzungen (down)   Hinweise (down)   Termine (down)   Themen (down)   Kontakt (down)

Aktuelles (up)

Für das Blockseminar wurden bisher die folgenden Themen vergeben:

Robert Meirich: "Hermite- und Smith-Normalform",
Markus Reuther: "Allgemeine Schnittebenen",
Christof Schulz: "Ungarische Methode",
Daniel Seidel: "Total unimodulare Matrizen",
Sebastian Schlüterbusch: "Matching".

Alle weiteren Themen (vgl. unter Pkt. Themen) sind noch wählbar.

Inhalt (up)

In diesem Seminar werden zentrale Artikel der kombinatorischen und ganzzahligen Optimierung behandelt, die starken Einfluss auf die Entwicklung dieses Gebietes hatten.

Voraussetzungen (up)

Grundkenntnisse in Graphen- und Netzwerkalgorithmen sowie kombinatorischer Optimierung. Für einige Themen sind Kenntnisse in linearer und ganzzahliger Optimierung notwendig.

Hinweise zu den Vorträgen (up)

Richtlinien für die Vortragsgestaltung und die Scheinvergabe: Bei der Literatursuche sind folgende Links nützlich:

Termine (up)

Die Vorbesprechung mit der Themenvergabe fand statt am Ein Probetermin mit Kurzvorträgen von jeweils 5 Minuten Dauer fand statt am Das Seminar wird als Blockseminar duchgeführt am Die Vorträge sind bis Mittwoch, den 09.07.2008 als PDF- oder PowerPoint-Datei bei Dr. Ralf Borndörfer einzureichen.

Themen (up)

Hinweis: Es werden zu den einzelnen Artikeln nur die jeweiligen BibTeX-Angaben angezeigt !
Eine Gesamtliste aller BibTeX-Angaben finden Sie hier
  1. Ungarische Methode
    The Hungarian Method for the assignment problem (Kuhn [1955]) (pdf)
    Algorithms for the Assignment and Transportation Problems (Munkres [1957]) (pdf)

  2. Matching
    Paths, Trees, and Flowers (Edmonds [1965]) (pdf) (pdf)
    Maximum Matching and a Polyhedron with 0,1 Vertices (Edmonds [1965]) (pdf)

  3. Perfekte Graphen
    Kap. 3 in Geometric Algorithms and Combinatorial Optimization (Grötschel, Lovász & Schrijver [1988]) (pdf)

  4. Submodulare Funktionen
    Submodular function minimization (Iwata [2008]) (pdf) (pdf)
    Submodular functions and convexity (Lovász [1983]) (pdf)
    A combinatorial algorithm minimizing submodular functions in strongly polynomial time (Schrijver [2000]) (pdf)
    A combinatorial strongly polynomial algorithm for minimizing submodular functions (Iwata, Fleischer & Fujishige [2001]) (pdf)

  5. Totale Unimodularität
    Kap. 19 & 20 in Theory of Linear and Integer Programming (Schrijver [1986]) (pdf)

  6. Reguläre Matroide & Totale Unimodularität
    Kap. 21 in Theory of Linear and Integer Programming (Schrijver [1986]) (pdf)

  7. Total duale Ganzzahligkeit und Hilbert-Basen
    Kap. 22 in Theory of Linear and Integer Programming (Schrijver [1986]) (pdf)

  8. Allgemeinen Schnittebenen
    Valid Inequalities for Mixed Integer Linear Programs (Cornuejols [2008]) (pdf) (pdf)

  9. Chvátal-Rang
    Bounds on the Chvátal Rank of Polytopes in the 0/1-Cube (Eisenbrand & Schulz [2003]) (pdf) (pdf)

  10. Hermite- und Smith-Normalform
    Kap. 4 in Theory of Linear and Integer Programming (Schrijver [1986]) (pdf)

  11. Basisreduktion
    Factoring polynomials with rational coefficients (Lenstra, Lenstra & Lovász [1982]) (pdf)
    Kap. 6 in Theory of Linear and Integer Programming (Schrijver [1986]) (pdf)

  12. Ganzzahlige Programmierung in fester Dimension
    Integer programming with a fixed number of variables (Lenstra [1983]) (pdf)
    Fast integer programming in fixed dimension (Eisenbrand [2003]) (pdf) (pdf)

  13. Ganzzahlige Punkte in Polyedern
    Lattice points, polyhedra, and complexity (Barvinok [2007]) (pdf) (pdf)

  14. Primale Methoden
    A Primal All-Integer Algorithm Based on Irreducible Solutions (Haus, Köppe & Weismantel [2003]) (pdf) (pdf)

Kontakt (up)


 
Sprechstunde
 Raum Telefon Email
Borndoerfer
 Dr. Ralf Borndörfer (www) n.V. ZIB 84185-243 borndoerferzib.de
Groetschel
 Prof. Dr. Martin Grötschel (www) n.V. MA 302 84185-210 groetschelzib.de
Zuletzt aktualisiert: 30. Mai 2008