Schedule for AMS 550.766

Schedule for AMS 550.766: Combinatorial Optimization, Spring 2020.

Here is the schedule of lectures :

PART I: Combinatorial Algorithms for Classic Problems

Lecture 1 (1/28/2020): (Sections 3.1, 3.2 of "4-Bill book", Section 4.2 in Lex Schrijver's notes, Lecture slides) What is Combinatorial Optimization? Motivating problems for Combinatorial Optimization (scheduling, transportation, astronomy, statistical/machine learning), Preliminaries on Graph theoretic terminology and run time of Algorithms, Definition and example of the max flow problem.
Lecture 2 (1/30/2020): (Section 3.2 of the "4-Bill book", Sections 4.2, 4.3 in Lex Schrijver's notes) Recap of maximum flow problem and example, Cuts and using cuts to upper bound flow, Flow incrementing/augmenting paths, Max Flow- Min Cut theorem, Theorem showing that max flow is reached if and only if no augmenting paths remain. Integrality of max flow when capacities are integral, The "naive" augmenting path algorithm, Bad example for showing "naive" augmenting path algorithm can take exponential (in the data) steps.
Lecture 3 (2/4/2020): (Write-up, Sections 4.4, 3.1 in Lex Schrijver's notes, Sections 3.3, 5.1 of the "4-Bill book") Shortest Augmenting path algorithm, 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: transportation problem, Military strategy problem (Problem 3.44 from textbook), Introducing the maximum matching problem.
Lecture 4 (2/6/2020): (Sections 3.3, 5.1 of the "4-Bill book", Secions 3.1 -- 3.4 in Lex Schrijver's notes) Matchings and Vertex covers, Curse of the odd cycle, Bipartite graphs, Apply Max flow-Min Cut to solve max matchings and min vertex covers in bipartite graphs and prove Konig's theorem. Matchings for general graphs, M-alternating paths, M-augmenting paths, M-augmenting path theorem for maximum matchings in general graphs, Motivation of M-alternating trees as a search tool for M-augmenting paths.
Lecture 5 (2/11/2020): (Section 5.2 from the "4-Bill book", Section 5.2 in Lex Schrijver's notes) Developing the tools for Edmonds' Blossom algorithm for maximum matching in non-bipartite graphs: M-alternating trees, Shrinking odd cycles, Expanding matchings from a contracted graph. Formal statement of Edmonds' Blossom algorithm for maximum matching.
Lecture 6 (2/13/2020): (Section 5.2 from the "4-Bill book", Sections 5.1, 5.2 in Lex Schrijver's notes) Proof of correctness of Edmonds' Blossom algorithm for maximum matching, Tutte-Berge formula as a consequence. Interpreting the max flow based bipartite matching algorithm (cardinality version) in terms of M-augmenting paths.
Lecture 7 (2/18/2020): (Section 3.2 in Lex Schrijver's notes) Running time discussion of Edmonds' matching algorithm, Hungarian Algorithm for weighted bipartite matching. Discussion of weighted combinatorial optimization problems: minimum cost flow, maximum weighted matching in general graphs.

PART II: Polyhedral Combinatorics

Lecture 8 (2/20/2020): (Sections 2.1, 2.2 and 2.3 from Lex Schrijver's notes, see also lines 288-358 in these notes) Convexity, Separating hyperplane theorem/Fundamental theorem of convexity in R^n, examples of convex sets: hyperplanes, halfspaces, Definition of polyhedra. Rank theorem for characterizing vertices of polyhedra. Convex hull.
Lecture 9 (2/25/2020): (Sections 2.3 and 2.4 from Lex Schrijver's notes, see also Sections 2.5.1 and 2.5.2 in these notes) Minkowski-Weyl theorem, Linear programming (LP), Vertex solutions to Linear Programs, motivating the dual linear program, weak duality. Valid inequalities/halfspaces, nonnegative combinations of an inequality system, Equivalence of valid inequalities and nonnegative combinations (characterization of valid inequalities for polyhedra). Proof of strong duality for linear programs.
Lecture 10 (2/27/2020): (Sections 2.4, 8.1, 8.2 from Lex Schrijver's notes, see also Sections 2.5.1 and 2.5.2 in these notes, Sections 6.1, 6.2, 6.5 from the "4-Bill book") Proof of characterization of valid inequalities, Abstract combinatorial optimization problems, Faithful embeddings of combinatorial optimization problems, Philosophy of Polyhedral Combinatorics, Example: Matchings. Linear Programming (LP) and Integer Programming (IP) formulations. IP formulation for matching, not necessarily LP formulation: triangle graph has non integer vertex. Totally unimodular matrices.
Lecture 11 (3/3/2020): (Section 1.4 from this book, Sections 8.1, 8.2, 8.3 from Lex Schrijver's notes, Sections 6.1, 6.2, 6.5 from the "4-Bill book") Totally Unimodular Matrices, Vertices are integral for totally unimodular constraint matrices A, Transformations that preserve the totally unimodular property, Linear programs and their duals with TUM constraint matrices. Bipartite matching polytope/TU-ness of incidence matrix of bipartite graph, 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.
Lecture 12 (3/5/2020): (Section 8.3, 8.4 from Lex Schrijver's notes, Sections 6.2, 6.5 from the "4-Bill book") Understanding the max flow LP, TU-ness of matrices with at most one +1 and one -1 in each column, 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 (3/10/2020): (Section 6.8 from the "4-Bill book", Section 7.5 from this book) Overview of Linear Programming algorithms: simplex method, ellipsoid method and interior point method, a crash course on the Ellipsoid algorithm ignoring many technical details, Solve LPs with polynomial number of calls to separation oracles, equivalence of optimization and separation (up to polynomial factors).
Lecture 14 (3/12/2020): Canceled due to COVID-19.
Lecture 15 (3/24/2020): (Zoom lecture notes, Section 25.1 and 25.2 in Lex Schrijver's "Combinatorial Optimization", Vol. A) Recap of LP/IP formulations of combinatorial optimization problems, Totally unimodualr matrices and applications to biparatite matching and max flow. Non-bipartite matching. Statement of matching polytope theorem that gives an LP formulation of the matching problem. Perfect matchings. Statement of perfect matching polytope theorem. Start of proof of perfect matching polytope theorem.
Lecture 16 (3/26/2020): (Zoom lecture notes, Section 25.1 and 25.2 in Lex Schrijver's "Combinatorial Optimization", Vol. A) Completing the proof of the perfect matching polytope theorem. Reducing the general matching problem to the perfect matching problem.
Lecture 17 (3/31/2020): (Zoom lecture notes, Sections 6.7, 6.8 from "4-Bill" book, Section 4.4 in in these notes, Section 5.2 and Chapter 7 from this book) Cutting plane method for solving integer programs; 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, Introducing Chvatal-Gomory cutting planes as a "non-combinatorial" way of getting cutting planes; convex hull of integer points in a rational halfspace, explicit formula for wirint Chvatal-Gomory cutting plane; Chvatal-Gomory sequence, Chvatal-Gomory closure. Deriving odd set inequalities for matching using CG procedure.
Lecture 18 (4/2/2020): (Zoom lecture notes, Section 6.7 from textbook, Section 5.2 from this book, Section 2.5 in these notes) Recap of definition of Chvatal-Gomory cutting planes, CG sequences; definition of CG proof. Chvatal-Gomory closures, Statement of completeness of Chvatal-Gomory procedure. Tools: Dimension of polyhedra, faces of polyhedra.
Lecture 19 (4/7/2020): (Zoom lecture notes, Section 6.7 from the "4-Bill" book, Section 5.2 from this book) Rotating C-G cut for face into a C-G cut for the full polyhedron. Proof of infeasibility certificate of integer points in a polytope using CG cutting planes.
Lecture 20 (4/9/2020): (Zoom lecture notes, Section 6.7 from the "4-Bill" book, Section 5.2 from this book) Proof of completeness of Chvatal-Gomory procedure. Proof of polyhedrality of the Chvatal-Gomory closure. Review of the Simplex Method for LP.
Lecture 21 (4/14/2019): (Zoom lecture notes, Sections 1.2.2, 5.2.4, 5.2.5 from this book, see also the surveys here and here) Gomory's fractional cuts, Cut generating functions.
Lecture 22 (4/16/2020): (Zoom lecture notes, Sections 1.2, 9.2, 5.1, 5.5 from this book): Branch and bound, Branch and Cut, Valid disjunctions, branching and cutting planes from general valid disjunctions, Cut generating linear programs (CGLP).

PART III: Other Techniques in Combinatorial and Discrete Optimization

Lattices and Algorithmic Geometry of Numbers

Lecture 23 (4/21/2020): (Zoom lecture notes, LaTex lecture notes, Section 9.1 from this book): Lattices: basic definitions and examples, Theorem for the existence of a basis of a lattice, Unimodular matrices connecting two bases, determinant of a lattice.
Lecture 24 (4/23/2020): (Zoom lecture notes, LaTex lecture notes, Section 9.1 from this book, and this book): Discussion of shortest vector problem and orthogonal/almost orthogonal bases, Orthogonality defect. Gram-Schmidt orthogonolization, Hadamard inequality showing defect is at least 1, Elementary column operations for bases and corresponding matrices, Normalization of a basis, Statement of Lovasz-Lenstra-Lenstra (LLL) algorithm, Proving upper bound of orthogonality defect at the end of LLL.
Lecture 25 (4/28/2020): (Zoom lecture notes, LaTex lecture notes, Section 9.1 from this book, and this book): Completing the proof of Lovasz-Lenstra-Lenstra (LLL) algorithm, Convex Integer Optimization; Lowner-John ellipsoidal approximations, Using the ellipsoid algorithm to compute approximate Lowner-John ellipsoids; Lenstra's algorithm for general convex integer optimization using ellipsoidal approximations and reduced lattice basis.
Lecture 26 (4/18/2019): (Zoom lecture notes, LaTex lecture notes, Section 9.1 from this book, and this book, Micciancio-Voulgaris CVP/SVP algorithm): Recap of Lenstra's algorithm; Convex optimization over lattices, Short discussion of shortest and closest lattice vector problems as special case problems with more efficient specialized algorithms running in single expoenntial time, conjectured single exponential complexity for general problem. Flatness theorem and dual lattices, improving 2^O(n^3) to 2^O(n log n) using 2^O(n) algorithms for CVP and SVP algorithms.