Module Handbook

  • Dynamischer Default-Fachbereich geändert auf MAT

Module MAT-52-12-M-7

Advanced Network Flows and Selfish Routing (M, 9.0 LP)

Module Identification

Module Number Module Name CP (Effort)
MAT-52-12-M-7 Advanced Network Flows and Selfish Routing 9.0 CP (270 h)

Basedata

CP, Effort 9.0 CP = 270 h
Position of the semester 1 Sem. irreg.
Level [7] Master (Advanced)
Language [EN] English
Module Manager
Lecturers
Area of study [MAT-OPT] Optimisation
Reference course of study [MAT-88.105-SG] M.Sc. Mathematics
Livecycle-State [NORM] Active

Courses

Type/SWS Course Number Title Choice in
Module-Part
Presence-Time /
Self-Study
SL SL is
required for exa.
PL CP Sem.
4V+2U MAT-52-12-K-7
Advanced Network Flows and Selfish Routing
P 84 h 186 h - - PL1 9.0 irreg.
  • About [MAT-52-12-K-7]: Title: "Advanced Network Flows and Selfish Routing"; Presence-Time: 84 h; Self-Study: 186 h

Examination achievement PL1

  • Form of examination: oral examination (20-30 Min.)
  • Examination Frequency: each semester
  • Examination number: 86110 ("Advanced Network Flows and Selfish Routing")

Evaluation of grades

The grade of the module examination is also the module grade.


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

Competencies / intended learning achievements

Upon successful completion of this module, the students have mastered advanced techniques used to compute network flows. They have studied and understand different approaches to network flows, especially those coming from game theory, with applications in traffic planning and economics. They are able to analyze the algorithms and to apply them to solve practical problems. They are able to critically assess the possibilities and limitations of the use of these algorithms. They understand the proofs presented in the lecture and are able to comprehend and explain them. In particular, they are able to outline the conditions and assumptions that are necessary for the validity of the statements.

By completing the given exercises, the students have developed a skilled, precise and independent handling of the terms, propositions and techniques taught in the lecture. In addition, they have learnt how to apply these techniques to new problems, analyze them and develop solution strategies independently or by team work.

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.

Requirements for attendance (informal)

Modules:

Requirements for attendance (formal)

None

References to Module / Module Number [MAT-52-12-M-7]

Course of Study Section Choice/Obligation
[INF-88.79-SG] M.Sc. Computer Science Formal Fundamentals [WP] Compulsory Elective
Module-Pool Name
[MAT-52-MPOOL-7] Specialisation Mathematical Optimisation (M.Sc.)
[MAT-AM-MPOOL-7] Applied Mathematics (Advanced Modules M.Sc.)