Computer Laboratory

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.