TUM – TUM – Menü

 

 
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:

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

Research Unit M9


Department of Mathematics
Boltzmannstraße 3
85748 Garching b. München
Germany
phone:+49 89 289-16858
fax:+49 089 289-16859
sekretariat-m9ma.tum.de

Professors

Prof. Dr. Peter Gritzmann
Applied Geometry and Discrete Mathematics

Prof. Dr. Andreas S. Schulz
Mathematics of Operations Research
(affiliated member of M9)

Prof. Dr. Stefan Weltge
Discrete Mathematics

News

April 2018
Case Studies 2018: Save the date: Case Studies poster presentation on May 25th, 2018, final workshop on July 7th, 2018.