Network Optimization
Calendar
- 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
SES # | TOPICS | KEY DATES |
---|---|---|
1 | Introduction to network models | |
2 | Computational complexity and data structures | |
3 | Graph search algorithms | Problem set 1 due |
4 | Transformations and flow decomposition | |
5 | Shortest paths: label setting algorithms | |
6 | The radix heap algorithm | |
7 | Shortest paths: label correcting algorithms | Problem set 2 due |
8 | Algorithm analysis | |
9 | Basic algorithms for the maximum flow problem | |
10 | Midterm 1 (Ses #1-8) | |
11 | Combinatorial applications of maximum flows | Project team and topic selection due |
12 | Preflow push algorithms | |
13 | More on preflow push algorithms | Problem set 3 due |
14 | Minimum cost flow: basic algorithms | |
15 | Minimum cost flow: polynomial time algorithms | Problem set 4 due |
16 | Applications of network flows; Linear programming review | |
17 | The network simplex algorithm | Project outline due |
18 | NP-completeness | |
19 | Midterm 2 (Ses #9-17) | |
20 | Lagrangian relaxation 1 | |
21 | Lagrangian relaxation 2 | |
22 | Multicommodity flows 1 | Problem set 5 due |
23 | Multicommodity flows 2 | |
24 | Presentations of class projects | Project report due |
25 | Presentations of class projects (cont.) |