Syllabus
- Introduction to network models
- Computational complexity and data structures
- Graph search algorithms
- Transformations and flow decomposition
- Shortest paths: label setting algorithms
- The radix heap algorithm
- Shortest paths: label correcting algorithms
- Algorithm analysis
- Basic algorithms for the maximum flow problem
- Combinatorial applications of maximum flows
- Preflow push algorithms
- More on preflow push algorithms
- Minimum cost flow: basic algorithms
- Minimum cost flow: polynomial time algorithms
- Applications of network flows; Linear programming review
- The network simplex algorithm
- Lagrangian relaxation 1
- Lagrangian relaxation 2
- Multicommodity flows 1
- Multicommodity flows 2
- Breadth first search
- Depth first search
- Topological ordering
- Eulerian cycles in directed graphs
- Flow decomposition
- Dijkstra's algorithm
- Dial's algorithm
- 2-level bucket algorithm
- Radix heap animation
- Label correcting algorithm
- Modified label correcting algorithm
- Ford-Fulkerson algorithm
- Preflow push algorithm
- Negative cycle (cycle canceling) algorithm
- Successive shortest path (SSP) algorithm
- Network simplex animations
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
ACTIVITIES | PERCENTAGES |
---|---|
Problem sets (5 total) | 24% |
Group project | 16% |
Midterms (2 total) | 60% |