|
Course Outline
Topics covered in the class
Jan. 10: Introduction and review of linear optimization.
Jan. 12: Combinatorial Optimization problems.
Jan. 17: Introduction of graphs and diagraphs; Shortest Path problem and Bellman's equation.
Jan. 19: Bellman's equation and Dijkstras's algorithm.
Jan 24: Rationale of Dijkstras's algorithms, complexity, more examples.
Jan 26: Lawler's version, complexity, Bellman-Ford algorithm.
Jan. 31: Rationale of Bellman-Ford algorithm
Feb. 2: Floyd-Warshall's algorithm for all pairs of nodes
Feb. 7: Minimum spanning trees and Kruskal's algorithms; rationale.
Feb. 9: Rationale of Prim's algorithms, Networks
Feb. 14: Network flow problem and FAP
Feb. 16: Minimum cut and maximal flow, proofs of theorems
Feb. 19-23: reading week.
Feb. 27: review and proofs of theorems, Ford-Fulkerson algorithm.
Mar. 2: More examples of Ford-Fulkerson algorithm.
Mar. 7: Cardinality matching problem.
Mar. 9: Midterm.
Mar. 14: More examples of Cardinality matching problems; complexity of Ford-Fulkerson algorithm preflows
Mar. 16: Preflows and distance labelling.
Mar. 21: The preflow push algorithm (Goldberg's algorithm)
Mar. 23: A complete example; Analysis of preflow push algorithm.
Mar. 28: Analysis of preflow push algorithm
Mar. 30: Transportation and Assignment problem.
Apr. 4: Hungarian algorithm; Incremental networks.
Apr. 6: Min cost flow by cycle algorithm; Network simplex method;
Apr. 11: Network Simplex Method; Review;
|