Skip to main content

Winter 2018/19

Algorithmen auf Graphen

Bachelorvorlesung im Wintersemester 2018/19
6 CP

Graphen sind ein wichtiges Modellierungswerkzeug in der Informatik und in den verschiedensten modernen Anwendungen. Ob wir einen Routenplaner, ein Smartphone oder Facebook nutzen, so stecken im Hintergrund Graphen und effiziente Verfahren, die graphentheoretische Probleme lösen.

Die Vorlesung gibt eine grundlegende Einführung in die Graphentheorie, die Modellierung von Praxisfragestellungen und Algorithmen zum Lösen dieser. Es werden insbesondere kombinatorische Optimierungsprobleme behandelt, die sich graphentheoretisch formulieren lassen und die mit Hilfe von Polynomialzeitalgorithmen optimal gelöst werden können. Dazu gehören bspw. kürzeste Wege, Rundreiseprobleme (Euler- und Hamiltonkreise), minimale Spannbäume, stabile und maximale Matchings und Flüsse in Netzwerken. Desweiteren werden Grundlagen der Komplexitätsheorie (P, NP, Vollständigkeit, Härte) mit Bezug auf Probleme in Graphen (Färben, Clique, TSP, Hamiltonkreis) behandelt.

Dozentin:

Assistent:

Zeit & Raum:

  • Mo 10-12 Uhr in Raum MZH 6190 (Vorlesung)
  • Di 10-11:30 Uhr in Raum MZH 1090 (Übung 1)

Start:

  • Dienstag, 16. Oktober 2018

Literatur:

  • [KV] Korte, Vygen: Kombinatorische Optimierung: Theorie und Algorithmen, Springer, 2012.
  • [KN] Krumke, Noltemeier: Graphentheoretische Konzepte und Algorithmen, Springer-Vieweg, 2012.
  • [CLRS] Corman, Leiserson, Rivest, Stein: Introduction to Algorithms, 3rd edition, MIT Press, 2009.
  • [KT] Kleinberg, Tardos: Algorithm Design, Pearson, 2006.
  • [AMO] Ahuja, Magnanti, Orlin: Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, 1993.

Ein- und Austragen von Prüfungsterminen in Stud.IP ist möglich bis zum 15. Februar, 12:00 Uhr.

Die Bearbeitung der Übungsblätter erfolgt in Gruppen von 2-3 Studierenden. Die Abgabe erfolgt in der Vorlesung am Montag eine Woche später.

DatumThema
16. OktoberEinführung, grundlegende Graphenbegriffe, Eulersche Graphen
22. OktoberGrundlagen Algorithmen, Korrektheitbeweise und Laufzeitanalyse, Breitensuche
29. OktoberKürzeste Wege, Dijkstra's Algorithmus
5. NovemberKürzeste Wege II (Bellman-Ford, Floyd-Warshall) und Bäume
12. NovemberMinimale aufspannende Bäume (Prim, Kruskal), Clustering
19. NovemberNetzwerkflüsse, Maximaler s-t-Fluss, Max Fluss = Min Schnitt
26. NovemberWeitere Flussprobleme, bipartite Graphen, Matchings
03. DezemberMatchings, Satz von König, Satz von Hall, M-augmentierende Wege
10. DezemberStabile Matchings, Gale-Shapley, Komplexitätstheorie
17. DezemberNP-schwere Graphenprobleme
7. JanuarProgrammieraufgabe (Keine Vorlesung/Übung)
14. JanuarNP-schwere Graphenprobleme II
21. JanuarApproximationsalgorithmen, Metrisches TSP, Christofides, Inapproximierbarkeit
28. JanuarHeuristiken für TSP (Nearest neighbor, Lokale Suche, Ausblick Metaheuristiken), Zusammenfassung

Algorithmic game theory

Advanced course in Winter 2018/19

Classic optimization theory assumes complete knowledge of the parameters of a problem and complete control over the outcome. In reality, these assumptions might fail and both information and decisions may be divided over different agents, each with their own objectives. These are the types of problems that we treat in algorithmic game theory.

This course offers an introduction into the field of algorithmic game theory. We develop an understanding of the core concepts in algorithmic game theory, such as equilibria, price of anarchy and price of stability, coordination mechanisms and auctions.

The core proficiencies that you will learn are
- identification of different types of equilibria,
- proving existence of pure Nash equilibria,
- proving upper and lower bounds on the price of anarchy for non-atomic routing games and smooth games,
- analyzing the second price and VCG auctions,
- analyzing revenue maximizing auctions.

Optionally, the seminar Highlights of Algorithms supplements this course very well by offering the chance to study in depth one specific result within the field of algorithmic game theory.

Students that want to extend the course to 8 ECTS (normally 6), should be present at the first meeting of the Highlights of Algorithms seminar (Thu 18.10 14:00 MZH 3150).

Lecturer:

  • Dr. Ruben Hoeksma

Time & Room:

  • Mon 14-16 in room MZH 1470
  • Tue 12-14 in room MZH 4140

Start:

  • Tuesday, October 16, 2018

Examination: is through a regular oral exam (Mündliche Prüfung).

Exercises: Exercises are not mandatory, yet highly recommended. Those students who obtain at least half of the points from the exercises receive an extra 0.3/0.4 on top of their grade from the oral exam. Those students who obtain at least 90 percent of the points from the exercises receive an extra 0.6/0.7 (total) on top of their grade from the oral exam. That is, for example, from 3.0 to 2.7 or 2.3, or from 2.7 to 2.3 or 2.0. The final grade cannot be improved beyond 1.0 and a grade of 5.0 cannot be improved.

Literature: The below literature serve as a great source for further reading. The course was based on parts of some of these.

DateTopic
16/10/18Introduction: Games and equilibria
22/10/18Relation between equilibria, Finding MNE, Potential games
23/10/18Atomic routing games, Exercise set 1
29/10/18Efficiency of equilibria, Non-atomic routing games, Price of anarchy
30/10/18Exercise set 2
05/11/18Bounds on POA for (non-)atomic routing games
06/11/18Exercise set 3
12/11/18Smoothness, Robust price of anarchy, Scheduling games
13/11/18Exercise set 4
19/11/18Coordination mechanisms in scheduling games
13/11/18Exercise set 5
26/11/18Mechanism design
27/11/18Exercise set 6
03/12/18VCG auctions
04/12/18Exercise set 7
10/12/18Revenue optimal auctions
11/12/18Computing revenue optimal auctions, Exercise set 8
17/12/18Simple near-optimal auctions
18/12/18Exercise set 9
07/01/19Mechanisms without money, house allocation, stable matching
08/01/19Exercise set 10
14/01/19   — 22/01/19NO LECTURE: reading assignment on voting + exercises (set 11 - due AT THE START of the lecture of 28/01/19!!)
28/01/19Exercise set 11
29/01/19Last lecture: recap and exam preparation

Proofs from the Book - Das Buch der Beweise (engl./dt.)

Proseminar in Winter 2018/19
4 CP

"Paul Erdős liked to talk about The Book, in which God maintains the perfect proofs for mathematical theorems, following the dictum of G. H. Hardy that there is no permanent place for ugly mathematics. Erdős also said that you need not believe in God but, as a mathematician, you should believe in The Book..." Aigner, Ziegler: Proofs from the BOOK.

Martin Aigner and Günter Ziegler published a book "Proofs from the BOOK" with candidates of such perfect proofs that contain brilliant ideas, clever insights, and wonderful observations. Many topics were suggested by Erdős himself, though he died before the book was written. The collection of problems spans number theory, geometry, analysis, combinatorics, and graph theory.

This seminar deals with a selection of topics from "Proofs from the BOOK". The presentations will be held either on a weekly basis or at the end of the semester in one or two full-day colloquia.

Lecturer:

Important: Kick-off Meeting: November 29, 2018, 9:00-12:00 in MZH 3150
Every participant gives a 5-min presentation on her/his topic. I give some general comments on how to give a (the final) scientific talk.

The actual presentations will be given on January 29, 2019, in room MZH 3150.

  • 09:30 Jan-Moritz Prade: Applications of Euler’s Formula
  • 09:30 Francisca Azocar: Cayley´s formula for the number of trees
  • 10:30 Jessica Winter: Five-coloring plane graphs
  • 10:30 Lucas Klemmer: A 1.5-Approximation for Path TSP
  • 11:30 Alexander Lindermayr: Max Cut
  • 13:30 Carl Hammann: Two-sided matching with one-sided preferences

The first meeting with all organizational details and an overview of topics took place on
Thursday, October 18, 2018 at 15:00h in room MZH 3150.

Literature:Aigner, Ziegler: Proofs from THE BOOK, 4. Auflage, Springer, 2009.

Diskrete Strukturen: Kombinatorik, Graphen, Färbungen

Proseminar im Sommersemester 2019
03-BE-699.13, 4 CP (+1 CP bei Zusatzleistung)


Das Seminar behandelt grundlegende Fragestellungen, Techniken und Resultate zu diskreten Strukturen. Zu den Themen gehören Kombinatorik, Induktion, Graphen, Bäume, Färbungen und Matchings. Beispiele für Fragestellungen sind:

  • Wie färbt man eine Landkarte mit wenigen Farben so dass benachbarte Länder verschiedene Farben haben?
  • Wie erhält man eine maximale Anzahl von Paaren (z.B. Zuordnungen von Arbeitnehmern und Arbeitgebern)?
  • Welche grundlegenden Möglichkeiten gibt es, kombinatorische Beweise zu führen?
  • Wie sortiert man eine Menge von Zahlen?
  • Wie zählt man Bäume?

Die Seminarvorträge werden in einer 1-2 tägigen Blockveranstaltung am Ende des Semesters bzw. am Beginn der Semesterferien gehalten. Details, Termine und Themen werden in der Vorbesprechung abgestimmt.
Dozent:

Termin:Mittwoch, 3. April 2019, 14:00-15:00 im MZH 3150 (einmalig), Vorbesprechung und Themenvergabe

Literaturgrundlage:

  • Lovász, Pelikan, Vesztergombi: Diskrete Mathematik, Springer 2005
  • Beutelspacher, Zschiegner: Diskrete Mathematik für Einsteiger, Vieweg-Teubner, 4. Auflage, 2011
  • Steger: Diskrete Strukturen 1, Springer, 2002

Shared Mobility: Modelle, Algorithmen und Optimierung

Masterprojekt Winter 2018

Inhalt dieses Projekts ist die Untersuchung von Anforderungen an IT-Unterstützungssysteme im Bereich der Shared Mobility. Es soll ein Überblick über aktuelle algorithmische Trends und Fragestellungen im Bereich der Shared Mobility, insbesondere E-Car-Sharing, gewonnen werden. Wir werden uns mit dem Aufstellen eigener Modelle für ausgewählte Optimierungsprobleme sowie mit der Entwicklung und Implementierung geeigneter Lösungsmethoden beschäftigen. Mögliche Schwerpunkte umfassen insbesondere, aber nicht ausschließlich, Heuristiken, Kombinatorische Optimierungsalgorithmen und Ganzzahlige Lineare Optimierung. Die entwickelten Lösungsverfahren sollen vor allem theoretisch (Worst-Case-Analyse und Kompetitivitätsanalyse) untersucht und ausgewertet werden, aber auch die Evaluation anhand von Praxisdaten ist möglich. Zur Unterstützung bei der Kalibrierung der Optimierungsprobleme sollen Parameter mittels Machine Learning bestimmt werden.

Nach einem Semester intensiver Arbeit ist das Projekt nun zu Ende. Auf dieser Webseite berichten die Studenten von ihrem Projekt.

Lecturers:

Assistent:

Projektraum: MZH 3240

Plenum: Fr 10-14 in Raum tba