Course pages 2012–13
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.
L110 Flows in Networks cannot be taken in conjunction with L107 Syntax and Semantics of Natural Language Processing in 2012-13.