Module Handbook

  • Dynamischer Default-Fachbereich geändert auf MAT

Course MAT-52-12-K-7

Advanced Network Flows and Selfish Routing (4V+2U, 9.0 LP)

Course Type

SWS Type Course Form CP (Effort) Presence-Time / Self-Study
- K Lecture with exercise classes (V/U) 9.0 CP 186 h
4 V Lecture 56 h
2 U Exercise class (in small groups) 28 h
(4V+2U) 9.0 CP 84 h 186 h

Basedata

SWS 4V+2U
CP, Effort 9.0 CP = 270 h
Position of the semester 1 Sem. irreg.
Level [7] Master (Advanced)
Language [EN] English
Lecturers
+ further Lecturers of the department Mathematics
Area of study [MAT-OPT] Optimisation
Additional informations
Livecycle-State [NORM] Active

Contents

  • basics of network flows,
  • efficient methods to compute max flows (Dinic's algorithm, Push-Relabel method),
  • polynomial and strong polynomial methods for min cost flows,
  • dynamic network flows (dynamic max-flow-min-cut theorem, temporally repeated flows) and networks expanded over time,
  • flows with flow-depending costs, Optimality criteria,
  • flows in Nash-equilibrium,
  • price of the anarchy (lower and upper bounds),
  • paradox of Braess and its consequences,
  • network design for selfish users,
  • congestion games

Literature

  • T. Roughgarden: Selfish Routing and the Price of Anarchy,
  • R. K. Ahuja, T. L. Magnanti, J. B. Orlin: Network Flows,
  • S. O. Krumke, H. Noltemeier: Graphentheoretische Konzepte und Algorithmen,
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest: Introduction to Algorithms.

Materials

Further literature will be announced in the lecture.

Requirements for attendance (informal)

Modules:

Requirements for attendance (formal)

None

References to Course [MAT-52-12-K-7]

Module Name Context
[MAT-52-12-M-7] Advanced Network Flows and Selfish Routing P: Obligatory 4V+2U, 9.0 LP