1. Introduction to Network Optimization (L1)
- based on chapter 1 of the course text
- establish terminology and basic notations
- discuss examples of key network models
- provide basics of linear network optimization
2. Shortest path problems (L2)
- based on chapter 2 of the course text
- highlight example application domains
- discuss major methods to address the problem
- discuss the performance of algorithms
3. The Max-Flow problem (L3)
- based on chapter 3 of the course text
- highlight example application domains
- discuss major methods to address the problem
4. The Min-Cost Flow problem (L4)
- based on chapter 4 of the course text
- discuss equivalent variants
- develop duality results in connection with the problem
5.Auction algorithm for Min-Cost Flow (L5)
- based on chapter 7 of the course text
- discuss algorithms design steps
- discuss variants of auction algorithm
6. Network flow arguments for bounding mixing times of Markov chains (L6)
- introduce the concept of mixing time of Markov chains
- conductance bounds and relation to eigenvalues
- multi-commodity flow and the method of canonical paths
7. Accelerated dual descent for network flow optimization (L7)
- review of Newton's method
- approximate Newton method based on network structure