Introduction to Network Optimization (L1) , (Download new notes), (Download course overview), (Download notes)
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
Shortest path problems (L2) (Download new notes), (Download notes 1), (Download notes 2)
based on chapter 2 of the course text
highlight example application domains
discuss major methods to address the problem
discuss the performance of algorithms
The Max-Flow problem (L3) (Download notes)
based on chapter 3 of the course text
highlight example application domains
discuss major methods to address the problem
The Min-Cost Flow problem (L4) (Download notes)
based on chapter 4 of the course text
discuss equivalent variants
develop duality results in connection with the problem
Auction algorithm for Min-Cost Flow (L5) (Download notes)
based on chapter 7 of the course text
discuss algorithms design steps
discuss variants of auction algorithm
Network flow arguments for bounding mixing times of Markov chains (L6) (Download notes)
introduce the concept of mixing time of Markov chains
conductance bounds and relation to eigenvalues
multi-commodity flow and the method of canonical paths
Accelerated dual descent for network flow optimization (L7) (Download notes) (Download related article)
review of Newton's method
approximate Newton method based on network structure
|