TUM – TUM – Menü

 

 
Optimierung in Netzwerken

Seminar

 

Dozenten: Prof. Dr. Peter Gritzmann
M.Sc. Paul Stursberg
Termin: Donnerstags, 12:15 -13:45 Uhr
Ort: MI 02.08.020
ECTS credits: 3

Aktuelles

  • 19. Juni 2015: Termine aktualisiert: Die Sitzung vom 2.7. wird verschoben auf Montag, den 29.6., 16:00 Uhr in Raum 02.06.020. Außerdem wurden die Vortragsthemen "Matching 2" und "Matching under Preferences" getauscht.
  • 16. April 2015: Termine aktualisiert (die Sitzung am 28.5. fällt aus).
  • 20. März 2015: Wir mussten Raum und Termin des Seminars noch einmal verschieben, und zwar auf Donnerstags, 12-14 Uhr, Raum MI 02.08.020.
  • 2. März 2015: Das Seminar findet in Raum MI 00.07.014 statt.
  • 19. Februar 2015: Der Semesterapparat in unserer Bibliothek befindet sich hier.
  • 18. Februar 2015: Die Themen- und Terminverteilung ist online, außerdem finden Sie unter Material genauere Inhaltsangaben und Literaturhinweise (siehe Literatur).
  • 28. Januar 2015: Ein erster Überblick über die Themengebiete sowie die Folien der Vorbesprechung sind online. Bitte senden Sie bis zum 1. Februar Ihre Themen-/Terminwünsche an stursbma.tum.de.
  • 13. Januar 2015: Details zur Vorbesprechung, erster Überblick über Termine.
  • 12. Januar 2015: Die erste Version dieser Homepage ist online.
Die Folien der Vorbesprechung finden Sie hier:pdf

Inhalte

Die Inhalte des Seminars werden sich großteils am Buch "Network Flows" von R. Ahuja, T. Magnanti, und J. B. Orlin orientieren. Grob wird das Seminar folgende Themengebiete umfassen:
  • Maximum Flow
  • Minimum Cost Flow
  • Network Transformations
  • Nichtlineare Kostenfunktionen
  • Generalized Flows (flows with gains and losses)
  • Multicommodity Flows
  • Matching-Probleme (bipartit, nicht-bipartit, Stable Marriage,...)
  • Routing-Probleme (z.B. Travelling Salesperson, Chinese Postman,...)
  • Scheduling-Probleme (Project Scheduling, Job-Shop-Scheduling,...)

Vorträge

Zu Beginn des Semesters wird ein einführender Termin abgehalten. Zu diesem wird jede/r Teilnehmer/in gebeten, sein Thema in einem fünfminütigen Kurzvortrag vorzustellen. Hierzu ist keinerlei Medieneinsatz zwingend erforderlich. Eine angemessene Vorbereitung dieser Kurzvorstellung ist trotzdem notwendig, insbesondere also eine grundlegende Einarbeitung in das Vortragsthema.

Ab dem zweiten Seminartermin wird zunächst je ein Vortrag pro Treffen angesetzt werden. Für die erfolgreiche Teilnahme am Seminar ist die Anwesenheit bei allen Terminen erforderlich. Die Terminplanung für die einzelnen Seminartermine ist wie folgt (eine genauere Beschreibung und Literaturangaben finden Sie unter Material zum Seminar:

Termin Thema Vortragender Anmerkungen, Material etc.
16.4. Kurzvorstellungen der Themen alle  
23.4. Network Transformations Patrick Wilson  
30.4. Maximum Flow Jakob Martin Sutka Folien: pdf
7.5. Minimum Cost Flow 1 Sophia Althammer  
21.5. Minimum Cost Flow 2 Yushan Liu  
11.6. Convex Cost Florian Pawlik  
18.6. Matching 1 Benedikt Mairhörmann  
25.6. Matching 2 Martin Bullinger Skript: pdf
29.6. Matching under Preferences Claudia Löschberger 16:00 Uhr, Raum 02.06.020
9.7. Generalized Flows Antonia Demleitner Folien: pdf
16.7. Multicommodity Flows Fabian Wagner  

Vortragsvorbereitung und -ablauf

Für jeden Vortrag ist (ohne Feedback) ein Zeitrahmen von 60 Minuten vorgesehen. Jede/r Vortragende ist verpflichtet, mindestens einen Besprechungstermin bis spätestens 3 Wochen vor dem Vortragstermin zu vereinbaren. Sowohl in der Wahl der Medien als auch bei der grundsätzlichen Vortragsgestaltung werden keine engere Vorgaben gestellt, das gleiche gilt für die Sprache, Vorträge können auf Englisch oder auf Deutsch gehalten werden.

Voraussetzungen

  • Algorithmische Diskrete Mathematik (MA2501)
  • Lineare Algebra (MA1101 und MA1102)
  • Analysis (MA1001 und MA1002)

Material zum Seminar

  • Themenaufteilung pdf

Literatur

  • R. Ahlswede, N. Cai, S.-Y. Li und R. W. Yeung. „Network information flow“. In: IEEE Transactions on Information Theory 46.4 (2000), S. 1204–1216.
  • R. Ahuja, T. Magnanti, J. B. Orlin. “Network flows: theory, algorithms, and applications”. Prentice Hall, 1993. Semesterapparat
  • D. Gale und L. Shapley. „College admissions and the stability of marriage“. In: The American Mathematical Monthly 69.1 (1962), S. 9–15.
  • R. W. Irving. „An efficient algorithm for the stable roommates problem“. In: Journal of Algorithms 6.4 (1985), S. 577–595.
  • K. Onaga. „Optimum flows in general communication networks“. In: Journal of the Franklin Institute 283.4 (1967), S. 308–327.
  • T. Radzik. „A Fast deterministic approximation for the multicommodity flow problem“. In: Mathematical Programming 78.1 (1996), S. 43–58.
  • T. Roughgarden. „Routing games“. In: Algorithmic game theory. Hrsg. von N. Nisan, T. Roughgarden, E. Tardos und V. V. Vazirani. Cambridge University Press, 2007. download 

-- PaulStursberg - 16 Apr 2015

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.