Research Institute for Discrete Mathematics

Module "Selected Topics in Discrete Mathematics (V5C2)"

Lecture Course

Optimization and Game Theory in Flow Problems

Winter term 2023/24

Flow problems are encountered in various real-life scenarios, including traffic management and logistics, and often necessitate a dynamic approach that considers the time-varying nature of the problem. Therefore, in this lecture, we will explore the concept of flows over time.
The first part of the lecture will focus on algorithms designed specifically for flow over time problems. We will examine both exact algorithms and approximation algorithms.
In the second part of the lecture we will explore flows (over time) from a game theoretical perspective. In situations like traffic, where there is no central authority dictating solutions, participants independently choose strategies or paths to minimize their own travel time. We will characterize and analyze the equilibria that emerge in such scenarios.

Time: Mondays, 10-12 am
Room: Seminar room, Lennéstr. 2
Prerequisites: Chapters 1-9 of the following book (in particular the chapters on network flows and linear programming): B. Korte, J. Vygen: Combinatorial Optimization: Theory and Algorithms. Springer, Sixth edition 2018

L. Vargas Koch