Course pages 2011–12
Flows in Networks
Principal lecturer: Dr Richard Gibbens
Taken by: MPhil ACS, Part III
Hours: 16 (14 lectures + 2 example classes)
Prerequisites: Familiarity with the basics of mathematical optimization problems, graph theory, game theory and packet-based communication networks
This module aims to provide a understanding of models for flows in networks and to illustrate these ideas by considering road and communication networks.
- Mathematical foundations: unconstrained and constrained optimization and equilibrium concepts [2 lectures]
- Applications to traffic assignment and road pricing in road transport networks. [4 lectures]
- Applications to computer packet networks including decentralised flow control and network utility maximization. [4 lectures]
- Mathematical foundations: game-theoretic notions of equilibrium, Braess's paradox and the price of anarchy for network problems. [4 lectures]
On completion of this module, students should:
- Have a broad understanding of how optimization and game theory underpin our understanding of diverse resource allocation problems in networks;
- have a familiarity with models for road and communication networks.
Coursework will take the form of two example sheets with two associated example classes.
Each assignment will form 25% of the overall result.
The lectured content will be assessed by written test, set and marked by the course leader. The mark will be expressed as a percentage and will form 50% of the overall result. The above two coursework assignments will each form 25% of the overall result.
Sheffi, Y. (1985). Urban transportation networks: equilibrium
analysis with mathematical programming methods.. Prentice-Hall.
Srikant, R. (2004). The Mathematics of Internet congestion control. Birkhauser.
Roughgarden, T. (2005). Selfish routing and the price of anarchy. MIT Press.