Lukas Graf M.Sc.

Wiss. Mitarbeiter
Diskrete Mathematik, Optimierung und Operations Research
Telefon: +49 (0)821 598-2230
E-Mail:
Raum: 3025 (L1)
Sprechzeiten: Derzeit im Homeoffice - bei Fragen per Mail erreichbar. Telefon/Zoom/Skype-Sprechstunden auf Anfrage.
Adresse: Universitätsstraße 14, 86159 Augsburg

Papers

  • A Finite Time Combinatorial Algorithm for Instantaneous Dynamic Equilibrium Flows (working paper)

    joint work with Tobias Harks

    We study the computational complexity of Instantaneous Dynamic Equilibria (IDE) and show that a natural extension algorithm needs only finitely many phases to converge leading to the first finite time combinatorial algorithm computing an IDE. We complement this result by several hardness results showing that computing IDE with natural properties is NP-hard.

  • The Price of Anarchy for Instantaneous Dynamic Equilibria (working paper)

    joint work with Tobias Harks

    We study the price of anarchy (PoA) for Instantaneous Dynamic Equilibria (IDE) and show an upper bound of order O(U⋅τ) for single-sink instances, where U denotes the total inflow volume and τ the sum of edge travel times. We complement this upper bound with a family of instances proving a lower bound of order Ω(U⋅logτ).

  • Dynamic Flows with Adaptive Route Choice (published)

    joint work with Tobias Harks and Leon Sering

    We study dynamic network flows and introduce a notion of instantaneous dynamic equilibrium (IDE) requiring that for any positive inflow into an edge, this edge must lie on a currently shortest path towards the respective sink. We measure current shortest path length by current waiting times in queues plus physical travel times. For single-sink networks we show existence and termination of IDE flows. For multi-sink networks we show existence and give an example for an instance where IDE flows never terminate.

If you find any mistakes in one of the papers or have any remarks on them, please do let me know. I am always thankful for all suggestions that might improve my work.

Talks

Upcoming:

  • WINE 2020 (Beijing), December „The Price of Anarchy for Instantaneous Dynamic Equilibria“
  • Dagstuhl-Seminar (Schloss Dagstuhl), September „Computational Complexity of Instantaneous Dynamic Equilibrium Flows“

2020:

  • Arbeitsseminar (Augsburg), June „Dynamic Flows with Adaptive Route Choice“ (Slides)

2019:

  • OR 2019 (Dresden), September: „Termination Time of IDE Flows in Single Sink Networks“ (Slides)
  • IPCO 2019 (Ann Arbor), May: „Dynamic Flows with Adaptive Route Choice“ (Slides)
  • DCGT 2019 (Potsdam), February: „Dynamic Flows with Adaptive Route Choice“ (Slides)

Curriculum Vitae

2017 - present: PhD Student

Since 2017 I am a PhD student of Tobias Harks at the University of Augsburg.

2014 - 2017: Mathematics M.Sc.

  • Master's Thesis: „Zusammenhänge von Auslastungs- und Potentialspielen“ (Connections between Congestion and Potential Games), supervisor: Tobias Harks (pdf | LaTeX-Files | Slides)
  • My personal notes for some of the lectures I attended during the course of my studies can be found here.
  • Teachings: Exercise classes to the lectures „Lineare Algebra I/II“, „Analysis I/II“, Informatik III (Computer Science III), „Kombinatorische Optimierung“ (Combinatorial Optimiziation), a lecture on differentiation and integration in a repetition course for Analysis I (Slides) and tutor at „Offener Matheraum“

2014: Internship at Munich Re

2011 - 2014: Mathematics B.Sc.

  • Bachelor's Thesis: „Der Satz von Gelfand-Neumark und eine Erweiterung für topologische Mannigfaltigkeiten“ (The Theorem of Gelfand-Neumark and an Extension for Topological Manifolds), supervisor: Kai Cieliebak (pdf | LaTeX-Files)
  • My personal lecture notes for some of the lectures I attended during the course of my studies can be found here.
  • Teachings: Exercise classes to the lectures „Logik für Informatiker“ (Logic for Computer Scientists) and „Einführung in die theoretische Informatik“ (Introduction to Theoretical Computer Sciences)

Suche