Course Description

Network flow problems form an important class of linear optimization problems with applications to several areas including chemistry, computer networking, engineering, public policy, scheduling, telecommunications, transportation, and many others. This course will provide an integrated view of the theory, algorithms, and the applications of key network optimization problems including the shortest path problem, the maximum flow problem, the minimum cost flow problem, the minimum spanning tree problem, and the multi-commodity flow problem. Most of the arguments will be presented from first principles, and we will adopt a network or graphical view point. Limited use of a linear programming approach will be involved, for which the necessary background materials will be reviewed. Emphasis will be on powerful algorithm strategies, rigorous analysis of the algorithms, and data structures for their implementation. Apart from problems involving proofs (in homework and exams), the student will be produce simple implementations of some of the algorithms (using MATLAB). Animations of algorithms will also be presented in order to help the student in gaining a sound intuition about them. Depending on student interest, we will discuss topics from combinatorial optimization as well.

Syllabus
Tentative Course Schedule
Topics covered in each class

Options to buy the text

Errors and typos in the AMO book

Scores against your password

MATLAB Codes
Example 1
Example 2
netdata.m
bfs.m
sp_dijkstra.m
FIFO_label_correcting.m
SPAugPath_MaxFlow.m
FIFO Preflow algo - main file
    preflow-push: functions:  maxflow_pref_ini.m,    maxflow_pref_find_active.m,    maxflow_pref__push_relab.m

Software
GIDEN