Ausgewählte Themen der Kombinatorischen Optimierung Seminar

 

Vortragstermine

Vortragsthemen

Dozent:	Prof. Dr. Raymond Hemmecke
Raum und Zeit:	MI , 02.04.011    Do, 14:15-15:45

Vorläufiger Vortragsplan

	Datum	Thema	Vortragende(r)
1	21.10.	Clustering mit instance-level Constraints	Christoph Bolkart
2	28.10.	Bin Packing	Max Schüßler
3	04.11.	Phylogenetische Bäume	Helene Maier
4	11.11.	Dichtebasiertes Clustering: DBScan	Marius Ritter
5	18.11.	Integer multi-commodity problem	Gabriel Guckenbiehl
6	25.11.	Hierarchisches Clustering: Ward	Philipp Krenz
7	09.12.	Universalität von 3-Weg-Transportproblemen	Stefan Franz
8	16.12.	Graph-Färbungen und Hilberts Nullstellensatz	Florian Brandl
9	13.01.	Heuristiken für das Traveling-Salesman-Problem (TSP)	Remy Lazarovici
10	20.01.	Sudoku als diskretes Optimierungsproblem	Paul Grünke
11	27.01.	FPTAS zur ganzzahligen Polynommaximierung	Tillmann Gaida
12	03.02.
13	10.02.
14	17.02.

Vortragsthemen

DISKRETE TOMOGRAPHIE

Generell lesenswert für alle Studenten zur Info über Diskrete Tomographie:

• DT_Intro1.PDF (5,8 MB) (Kapitel 1 aus dem Buch: Discrete Tomography: Foundations, Algorithms, and Applications, Birkhäuser Boston, 1999)
• DT_Intro2.PDF (2,4 MB) (P. Gritzmann, Discrete tomography, AvH?-Magazin 66 (1995), 23-32)

Thema 1: Diskrete Tomographie in 2D (Betreuer: Andreas Alpers)

• Algorithmus und Problemstellung aus DT_Intro1.PDF (5,8 MB) und Beweis der polynomiellen Laufzeit aus der totalen Unimodularitaet des Ax=b Systems. Der Beweis (und 4 andere Varianten) sind in 2D_DT.pdf (1,9 MB) (aus: Sven de Vries, Discrete tomography, packing and covering, and stable set problems polytopes and algorithms, Dissertation, TU München, 1999. ) zu finden.

Thema 2: Instabilität in der diskreten Tomographie (2D, m>=3 Richtungen) (Betreuer: Andreas Alpers)

• Basiert auf Artikel (0,2 MB) (A. Alpers, P. Gritzmann, L. Thorens: "Stability and Instability in Discrete Tomography," Lecture Notes in Computer Science 2243; Digital and Image Geometry (Advanced Lectures), G. Bertrand, A. Imiya, R. Klette (Eds.), pp. 175--186, Springer-Verlag, 2001)

Thema 3: Sudoku als diskretes Optimierungsproblem (Betreuer: Andreas Alpers)

• Basiert auf Artikel (0,1 MB) (Sudoku: Strategy Versus Structure By: J. Scott Provan, in American Mathematical Monthly, October 2009)

Thema 4: Zusammenhang Diskrete Tomographie und einem alten (ungelösten) Zahlentheorie-Problem (Betreuer: Andreas Alpers)

• Basiert auf Artikel (0,1 MB) (A. Alpers, R. Tijdeman: "The Two-Dimensional Prouhet-Tarry-Escott Problem," Journal of Number Theory, 123 (2), pp. 403-412, 2007).

CLUSTERING

Generell lesenswert für alle Studenten zur Info über Clustering:

• Artikel (0,6 MB)

Thema 5: partitionierendes Clustering: k-means (Betreuer: Steffen Borgwardt)

• Artikel (1,3 MB)
• Grundlagen des partitionierenden Clusterings
• k-means: Funktionsweise, Laufzeit, Eigenschaften
• Erweiterungen von k-means
• Beispiele und Anwendungen

Thema 6: hierarchisches Clustering: Ward (Betreuer: Steffen Borgwardt)

• Artikel (0,8 MB)
• Grundlagen des hierarchischen Clusterings
• Dendogramme, agglomerierendes und aufteilendes Clustering
• Ward: Funktionsweise, Laufzeit, Eigenschaften
• Beispiele und Anwendungen

Thema 7: fuzzy Clustering: FCM (Betreuer: Steffen Borgwardt)

• Artikel (1,1 MB)
• Unterschiede von fuzzy Clustering und hard Clustering
• FCM: Funktionsweise, Laufzeit, Eigenschaften
• Beispiele und Anwendungen

Thema 8: Clustering mit instance-level Constraints (Betreuer: Steffen Borgwardt)

• Artikel (0,7 MB)
• Arten von instance-level Constraints
• Modellierung 'anderer' Nebenbedingungen durch instance-level Constraints
• Anwendung zur 'Lenkung' von Clustering-Algorithmen
• Erweiterung klassischer Algorithmen um instance-level Constraints
• Beispiele und Anwendungen

Thema 9: dichtebasiertes Clustering: DBScan (Betreuer: Michael Öllinger)

• Artikel (0,1 MB)
• Grundlagen des dichtebasierten Clusterings
• DBScan: Funktionsweise, Laufzeit, Eigenschaften
• Beispiele und Anwendungen
• verwandte Algorithmen

SONSTIGE THEMEN

Thema 10: Universalität von 3-Weg-Transportproblemen (Betreuer: Raymond Hemmecke)

• Artikel (0,2 MB)
• Transformation IP in 3xMxN Transportproblem
• Komplexität für feste und variierende M und N
• Zusammenhang zu Diskreter Tomographie in 3D

Thema 11: Optimalitätszertifikate und N-fache IP (Betreuer: Raymond Hemmecke)

• Artikel (0,5 MB)
• Definition Optimalitätszertifikat
• Graverbasen als Optimalitätszertifikat
• Anzahl der Verbesserungsschritte
• N-fache IPs

Thema 12: Heuristiken für das Traveling-Salesman-Problem (TSP) (Betreuer: Raymond Hemmecke)

• TSP  (für einen kurzen Einblick und ein paar Referenzen)
• Problembeschreibung
• Überblick über die wichtigsten Heuristiken

Thema 13: Graph-Färbungen und Hilberts Nullstellensatz (Betreuer: Raymond Hemmecke)

• Artikel (0,3 MB)
• Färbungen von Graphen, Färbungszahl
• Polynomiale Gleichungssysteme zur Modellierung des Problems
• Hilberts Nullstellensatz als Negativ-Zertifikat (also für Nicht-Färbbarkeit mit k Farben)

Thema 14: LLL-Algorithmus und Anwendung (Betreuer: Raymond Hemmecke)

• Artikel 1 (0,2 MB)
• Artikel 2 (0,1 MB)
• Vorstellung LLL-Algorithmus (Basisreduktion)
• Bezug zu Gram-Schmidt-Verfahren
• Anwendung, z.B. Reformulierung von IPs

Thema 15: Phylogenetische Bäume (Betreuer: Raymond Hemmecke)

• Phylogenetischer Baum  (für einen kurzen Einblick und ein paar Referenzen)
• Einführung in die Problematik
• Neighbor-Joining-Algorithmus

Thema 16: Bin Packing (Betreuer: Raymond Hemmecke)

• Bin Packing  (für einen kurzen Einblick)
• Literatur: Bernhard Korte, Jens Vygen: Kombinatorische Optimierung. Springer, Berlin Heidelberg 2008, ISBN 978-3-540-76918-7, S. 485ff
• Problembeschreibung
• Heuristiken/Approximationsverfahren