Course Meeting Times

Lectures: 2 sessions / week, 1.5 hours / session

Prerequisites

6.251J/15.081J Introduction to Mathematical Programming or a course on data structures.

Subject Description and Goals

15.082J/6.855J/ESD.78J is a graduate subject in the theory and practice of network flows and its extensions. Network flow problems form a subclass of linear programming problems with applications to transportation, logistics, manufacturing, computer science, project management, and finance, as well as a number of other domains. This subject will survey some of the applications of network flows and focus on key special cases of network flow problems including the following: the shortest path problem, the maximum flow problem, the minimum cost flow problem, and the multi-commodity flow problem. We will also consider other extensions of network flow problems.

The goals of the subject are the following:

• To present students with knowledge of the state-of-the-art in the theory and practice of solving network flow problems.
• To provide students with a rigorous analysis of network flow algorithms.
• To help each student develop his or her own intuition about algorithm development and algorithm analysis.

Textbook

Ahuja, Ravindra K., Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Upper Saddle River, NJ: Prentice Hall, 1993. ISBN: 9780136175490.

Grading