Course pages 2012–13
Flows in Networks
Principal lecturer: Dr Richard Gibbens
Taken by: MPhil ACS, Part III
Code: L110
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
Aims
This module aims to provide a understanding of models for flows in networks and to illustrate these ideas by considering road and communication networks.
Syllabus
- 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]
Objectives
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
Coursework will take the form of two example sheets with two associated example classes.
Each assignment will form 25% of the overall result.
Practical work
None.
Assessment
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.
Recommended reading
Sheffi, Y. (1985). Urban transportation networks: equilibrium
analysis with mathematical programming methods.. Prentice-Hall.
Available online.
Srikant, R. (2004). The Mathematics of Internet congestion control.
Birkhauser.
Roughgarden, T. (2005). Selfish routing and the price of anarchy.
MIT Press.
Note:
L110 Flows in Networks cannot be taken in conjunction with L107 Syntax and Semantics of Natural Language Processing in 2012-13.