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.