Schedule for AMS 550.666: Combinatorial Optimization, Fall 2014.



Here is the schedule of lectures :

PART I: Combinatorial Algorithms for Classic Problems

Lecture 1: (Sections 3.1, 3.2 of textbook, slides) What is Combinatorial Optimization? Motivating problems for Combinatorial Optimization (transportation, transshipment, scheduling, astronomy), Preliminaries on Graph theoretic terminology and run time of Algorithms, Definition of the flow problem, basic notation, using partitions or cuts to upper bound flow.
Lecture 2: (Section 3.2 of textbook) Cuts, Flow incrementing/augmenting paths, Max Flow- Min Cut theorem, The "naive" augmenting path algorithm, Analysis of algorith showing it returns max flow and provides the min-cut, Bad example for showing "naive" augmenting path algorithm can take exponential (in the data) steps, Shortest Augmenting path algorithm, Beginning the proof running time of shortest augmenting path.
Lecture 3: (Section 3.2, 3.3 of textbook, write-up) Finish proof of O(nm^2) run time for the shortest augmenting path algorithm (see this write-up for some of the details. This write-up is inspired by Lex Schrijver's proof on page 66 of these notes), Application of flow: transshipment problem, the attacker problem.
Lecture 4: (Section 3.3, 5.1 of textbook) Matchings and Vertex covers, Curse of the odd cycle, Bipartite graphs, Statement of Konig's theorem for bipartite graphs, Using Max flow to find maximum matching in bipartite graphs, Apply Max flow-Min Cut to prove Konig's theorem. Matchings for general graphs, M-alternating paths, M-augmenting paths, Statement of M-augmenting path theorem for maximum matchings in general graphs. Beginning the proof of M-augmenting path theorem for maximum matchings in general graphs.
Lecture 5: (Section 5.1 of textbook) Proof of M-augmenting path theorem for maximum matchings in general graphs, Motivate Tutte-Berge formula as a generalization of the vertex cover bound for matching, shrinking operation of odd cycles, Tight odd cycles, characterization of tight odd cycles.
Lecture 6: (Section 5.1, 5.2 from textbook) Essential and inessential vertices, Lemma 5.5 of textbook on existence of tight odd cycles from inessential vertices, Proof of Tutte-Berge formula. M-alternating trees as a search tool for M-augmenting paths, understand the four possibilities: extending a tree, augmenting a matching, shrinking an odd cycle, frustrated M-alternating tree.
Lecture 7: (Section 5.2 from textbook) Establish structural results for odd-cycle-shrinking and frustrated trees, Edmonds' Blossom algorithm for maximum matching in general graphs, proof of correctness of the Blossom algorithm.

PART II: Polyhedral Combinatorics

Lecture 8: (Sections 2.1 and 2.2 in Lex Schrijver's notes) Convexity, Separating hyperplane theorem/Fundamental theorem of convexity in R^n, examples of convex sets: hyperplanes, halfspaces, Definition of polyhedra, extreme points/vertices, rank theorem for characterizing vertices of polyhedra, Minkowski-Weyl theorem (without proof).
Lecture 9: (Section 2.3 from Lex Schrijver's notes) Affine independence, Dimension of convex sets. Convex cones, Farkas' Lemma and its proof, Characterizing valid inequalities for polyhedra.
Lecture 10: (Sections 2.4 from Lex Schrijver's notes) Certificate of infeasibility for polyhedra, Linear Programming, motivate the dual LP, Characterization of infeasibility, finiteness and unboundedness of primal and dual linear programs, Geometry of linear programming and duality, Vertex solutions to LPs, quick mention of LP algorithms - simplex, ellipsoid, interior-point methods.
Lecture 11: (Sections 8.2, 8.3, from Lex Schrijver's notes, Sections 6.1, 6.5 from textbook) Philosophy of Polyhedral Combinatorics, Integer Programming, Totally Unimodular Matrices, Vertex solution are integral for totally unimodular constraint matrices A, Transformations that preserve the totally unimodular property, Bipartite matching integer program, TU-ness of contraint matrix.
Lecture 12: (Section 8.3, 8.4 from Lex Schrijver's notes, Sections 6.2, 6.3 from textbook) Proofs for operations that preserve TU-ness, Bipartite matching LP, intepret dual LP as the vertex cover problem, use TU-ness and LP duality to prove Konig's theorem: max-matching = min vertex cover for bipartite graphs. TU-ness of matrices with at most one +1 and one -1, understanding the max flow LP, use TU-ness and integrality of optimal solutions to get min cut from dual of max flow LP, use LP duality to derive max flow-min cut.
Lecture 13: (Section 8.3 from Lex Schrijver's notes, Section 6.3 from textbook) Discussion of general matching polytope, odd-set inequalities, Statement of Edmond's Matching Polytope Theorem. Separation oracles, Ellipsoid algorithm, Solve LPs with polynomial number of calls to separation oracles, minimum odd cut algorithm as separation oracle for matching polytope. A crash course for the ellipsoid algorithm (ignoring all technical details).
Lecture 14: (Section 6.7 from textbook) Using combinatorial insight to get cutting planes for integer programs modeling combinatorial optimization problems, examples: odd-set inequalities for matching, clique inequalities for stable set, cover inequalities for knapsack problems, question of separation oracle for a family of cutting planes, Chvatal-Gomory cuts as a "non-combinatorial" way of getting cutting planes. Odd set inequality for matching as a special case. Chvatal closures, Chvatal rank of a valid inequality for the integer hull, completeness of the Chvatal-Gomory procedure.
Lecture 15 (Section 1.2.2 in Chapter 1 from the book Integer Programming): Review of the Simplex Method for LP, Gomory's fractional cuts.
Lecture 16 (Section 1.2.3 in Chapter 1 from the book Integer Programming): Subadditive function cuts, Branch and Cut.

PART III: Other Techniques in Combinatorial Algorithms

Semidefinite Programming Relaxations for integer programs and combinatorial optimization

Lecture 17 (Sections 10.1 and 10.2.2 from the book Integer Programming): Positive semi-definite matrices, Semidefinite programs (SDPs), Stable Set problem: using quadratic constraints (optimization problem with quadratic polynomial constraints), relaxing the polynomial optimization problem to an SDP.
Lecture 18 (Section 10.1 and 10.2.2 from the book Integer Programming): Showing that stable set SDP as strong as clique inequality system, separation oracle for applying ellipsoid algorithm to solve SDP.
Lectures 19, 20: No lectures - Instructor away for conference.
Lecture 21 (Section 10.2.1 and 10.3 from the book Integer Programming): Goemans-Williamson Max-Cut algorithm using SDPs, Lovasz-Schrijver hierarchies, Combinatorial structures/ Set systems; additive/linear combinatorial optimization.

Matroids

Lecture 22: (Section 10.1 from Lex Schrijver's notes) Combinatorial structures/ Set systems; additive/linear combinatorial optimization; Independence/down-monotone systems; Bases, Circuits, matroid condition and matroids; Basis replacement lemma; Proof that matroid condition is equivalent to the greedy algorithm returning optimal solution. Example: Forests in a graph.
Lecture 23: (Section 10.3, 10.5 from Lex Schrijver's notes) Rank function, Connection between antichains and bases and circuits of independence systems, Examples of Matroids: Graphic matroid, Graphic matroid, Transversal matroid, Partition matroid, Linear matroid; Matroid Intersection problem -- definition and examples: Bipartite matching (intersection of two partition matroids), Common system of distinct representatives (intersection of two transversal matroids), Arborescences, a.k.a "rooted" trees in directed graphs (intersection of a graphic matroid and a partition matroid).

Here are two papers that apply matroid intersections to solve wirless networking: Paper I and Paper II (the second paper expands on the ideas of the first paper).

Lecture 24: (Section 10.2 from Lex Schrijver's notes) Equivalent axioms for the matroid condition on bases, circuits and rank functions; Dual matroids.
Lecture 25: (Sections 10.4, 10.5 from Lex Schrijver's notes) "Unique Perfect Matching" lemma for independent sets of a matroid, Matroid Intersection Algorithm -- statement and beginning the proof.
Lecture 26: (Sections 10.4, 10.5 from Lex Schrijver's notes) Matroid intersection algorithm -- finish proof of its correctness; Matroid Intersection theorem, Deriving Konig's theorem for bipartite graphs from the Matroid Intersection Theorem. Few comments about matroid union.