Homepage of APM 6664

APM 6664, Winter 2018

The authors of the text has a webpage for the book including a list of typographical errors.

Lectures

Jan 3: Review of LP: Fourier-Motzins Elimination, Farkas' Lemma.

Jan 8: Review of LP: Farkas' Lemma, Strong Duality Theorem, Fundamental Theorem of Linear Programming, Complementary Slackness.

Jan 10: Minimum weight spanning tree problem, Kruskal's algorithm, Prim's algorithm, basic polyhedral concepts.

Jan 15: Basic polyhedral concepts, spanning tree polytope

Jan 17: Shortest paths, feasible potentials, Ford algorithm. Jan 17: Shortest paths, feasible potentials, Ford algorithm, Bellman-Ford algorithm.

Jan 22: Linear programming and shortest path, Dijkstra's Algorithm, maximum flow and minimum cut problems.

Jan 24: Ford-Fulkerson Algorithm, max-flow-min-cut theorem.

Jan 29: Edmonds-Karp modification, duality proof of the max-flow-min-cut theorem, complementary slackness proof of the max-flow-min-cut theorem.

Jan 31: Another proof of the max-flow-min-cut theorem, Gale's Theorem, Hoffman's Theorem.

Feb 5: More feasibility results, min-flow-max-cut theorem, Konig's Theorem, Hall's Theorem.

Feb 7: Perfect matching algorithm for bipartite graphs, weighted perfect matching algorithm for bipartite graphs.

Feb 12: Maximum cardinality matching algorithm for bipartite graphs, weighted matching algorithm for bipartite graphs, Tutte's Theorem, perfect matching algorithm for general graphs.

Feb 14: Weighted perfect matching algorithm for general graphs, Tutte-Berge Formula, maximum cardinality matching for general graphs.

Feb 26: Midterm Test.

Feb 28: Edmonds-Gallai Decomposition, maximum weight matching for general graphs.

Mar 5: VLSI presented by Professor Steffy.

Mar 7: Anderson's proof of Tutte's Theorem, Schrijver's proof of Tutte-Berge Formula, equivalency between Tutte's Theorem and Tutte-Berge Formula.

Mar 12: Minimum Cost Flow Problem, optimality condition, negative cycle cancellation algorithm (basic version, pseudo polynomial).

Mar 14: Primal-Dual minimum cost flow algorithm (basic version, pseudo polynomial), reduction to the transshipment problem.

Mar 19: Successive Scaling Algorithm for minimum cost flow problem (polynomial time).

Mar 21: Scale-and-Shrink minimum cost flow problem (strongly polynomial time), Gomory-Hu trees.

Mar 26: Special office hours.

Mar 28: Chinese Postman Problem, Karger's Algorithm for finding unrestricted minimum cuts.

April 2: Node identification algorithm for finding unrestricted minimum cuts, weighted T-join problem.

April 4: Seymour's min-max theorem on packing T-cuts in bipartite graphs, Lovasz' Theorem.

April 9: Augmentation problems, Frank's algorithm.

April 11: Lovasz' Splitting Off Theorem.

April 16: Successive augmentation problem for undirected graph, edge connectivity version.