TUM – TUM – Menü
 
Ausgewählte Themen der diskreten Optimierung

Seminar

 

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

Inhalt

Ziel des Seminars ist ein Überblick über verschiedene Probleme und Ansätze in der diskreten Optimierung. Mögliche Themen beschäftigen sich mit Packungsproblemen, Maschinenlernen oder algebraischen Ansätzen.

Voraussetzungen

  • Algorithmische Diskrete Mathematik (MA 2501)
  • Lineare Optimierung (MA 3501)

Vorläufiger Vortragsplan

Datum Thema Vortragende(r)
1 28.11. Dichtebasiertes Clustering Alexander Kumpf
2 28.11. t.b.a. Kevin Strauß
3 05.12. Sudoku als ILP Alexandra Steil
4 05.12. Heuristiken für das TSP Daniel Schmidt genannt Waldschmidt
5 19.12. Graphfärbungen und Hilberts Nullstellensatz Carolin Görnig
6 19.12. Phylogenetische Bäume Martin Sutter
7 16.01. Bin Packing Christopn Faltermeier
8 16.01. Crew Scheduling Szymon Albinski
9 23.01. Partitionierendes Clustering Stefan Tilly
10 23.01. Hierarchiches Clustering Christian Treubel
11 30.01. Diskrete Tomographie Ludwig Bayer
12 30.01. t.b.a. Kilian von Bibra

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

  • 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)

  • 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

  • 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

  • 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

  • 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

  • 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

  • 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

  • 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

  • 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

  • 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

  • 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)
  • TSP  (für einen kurzen Einblick und ein paar Referenzen)
  • Problembeschreibung
  • Überblick über die wichtigsten Heuristiken

Thema 13: Graph-Färbungen und Hilberts Nullstellensatz
  • 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

  • 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

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

Thema 16: Bin Packing
  • 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.