Combinatorial Optimization - Structures and Algorithms

Fall 2011, TuTh 4:35-5:55, CCB 102

Aug 23, 25, 30, Sep 1 Notes 1-4 Elementary properties of 2-edge-connected undirected graphs and strongly connected directed graphs. Degree constrained orientations. Minimum cut in undirected graphs.
Sep 6, 8, 13 Notes 5-7 Representation of minimum cuts. Gomory-Hu trees. Sparse certificates for edge- and node-connectivity. SFS trees. Chordal graphs.
Sep 13, 15, 20 Notes 7-9 Lucchesi-Younger theorem with algorithmic proof. Conservative costs.
Sep 20, 22 Lectures 9-10 Matroid theory basics: independence, cycle & rank axioms. Examples. Connected matroids. Operations: deletion, contraction, direct sum, truncation. Dual matroids.
Sep 27, 29 No class.
Homework set Homework 1
Oct 4 Lecture 11 Greedy algorithm for matroids and polymatroids. Matroid and submodular polyhedra, matroids from polymatroids. Rado's theorem. Homomorphic image of matroids. Matroid partition theorem.
Oct 6 Lecture 12 Applications for matroid partition: packing and covering by trees. Matroid intersection, equivalence to matroid partition. Edmonds' algorithm for matroid intersection. Min-max formula for maximum weight common bases.
Oct 13 Lecture 13 Rooted k-edge connected subgraphs. Matroids from non-monotone submodular functions and from intersecting submodular functions. Truncation of intersecting submodular functions. Applications: source location, count matroids, rigidity matroid, Lovasz-Yemini theorem.
Oct 18 Lecture 14 Basics on integer polyhedra. TU-matrices: bipartite and directed graphs, network matrices and applications. TDI systems.
Oct 20 Lecture 15 TDI systems continued. Submodular flows. Edmonds-Giles theorem. Applications: flows, matroid intersection, Lucchesi-Younger, Nash-Williams's weak orientation theorem. See also lecture notes on Chandra Chekuri's website.
Oct 25 Lecture 16 Undirected splitting off: Lovász's theorem. Applications: constructive characterization of 2k-edge-connected graphs, Nash-Williams's weak orientation theorem. Mader's theorem on minimal k-edge-connected graphs.
Oct 27 Lecture 17 Undirected edge-connectivity augmentation. Degree-constrained version. Watanabe-Nakamura theorem. Matroidal structures. Minimum cost version for node-induced costs. Optimal augmentations with upper and lower bounds. Mader's undirected splitting off theorem (formulated).
Nov 1 no lecture Ravi Kannan's talk.
Nov 3 Lecture 18 Proof of Mader's undirected splitting off theorem.
Nov 8 Lecture 19 Undirected local edge-connectivity augmentation. Frank's theorem. Applications of splitting off: edge-disjoint Steiner-trees. Lovasz-Cherkassky theorem on T-paths.
Nov 10 no lecture Avi Wigderson's talk
Homework set Homework 2
Nov 15,17 no lecture
Nov 22,29 Lectures 20-21 Mader's directed splitting off theorem. Directed edge-connectivity augmentation. Coverings of positively crossing supermodular set functions: degree prescribed version (Thm. 17.2.1) and minimum cardinality version (Thm. 17.2.8). Applications: subset connectivity, (k,l)-edge-connectivity.
Nov 24 Thanksgiving
Nov 29, 30 Lectures 21-22 Directed node-connectivity augmentation. Notion of set pairs: uncrossing, independence. Bisub/supermodular functions. Frank-Jordan theorem on covering positively crossing supermodular functions on set pairs. Applications: directed node-connectivity, ST-edge-connectivity augmentation, covering set pair functions.
Dec 1 no lecture Ruta Mehta's talk
Dec 5 Lecture 23 Gyori's theorems on generating path systems and on covering vertically convex rectilinear polygons. Frank's algorithm for finding an optimal solution.

László Végh