Course pages 2014–15
Flows in Networks
Principal lecturer: Dr Richard Gibbens
Additional lecturer: Dr Andrei Bejan
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 an 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.
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 80% of the overall result. Each example sheet will be ticked (pass/fail) and worth 10% 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.