Prerequisites:

MATH 308, MATH 345, CMPT 225.

Textbook:

Network Flows: Theory, Algorithms and Applications by R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Prentice Hall 1993.

Course Description:

Applications of Network flow models; flow decomposition; polynomial algorithms for shortest paths, maximum flows and minimum costs flows; convex cost flows; generalized flows; multi-commodity flows.

Outline:

Network flow models and applications, developing polynomial time algorithms, flow decomposition theorems.

Shortest path algorithms: Review of Dijkstra’s algorithm and implementations, label correcting algorithms and special implementations, detection of negative cycles.

Maximum Flows: Review of augmenting path algorithms labeling algorithms, labeling algorithm and maximum flow minimum cut theorem, capacity scaling, pre-flow push algorithms, flows in unit capacity networks.

Minimum cost flows: Optimality conditions and duality, cycle-canceling algorithm and minimum mean cycle canceling, capacity scaling algorithm.

Convex cost flows and transformation to minimum cost flows, generalized network flow models and properties of basic feasible solutions, multi-commodity network flow models.

Additional applications of Network flow models.

Grading Scheme

Assignments - 20%

Midterm Test - 20%

Project Presentation - 20%

Final Exam - 40%

THE INSTRUCTOR RESERVES THE RIGHT TO CHANGE ANY OF THE ABOVE INFORMATION