everything.study
18.997

Topics in Combinatorial Optimization

Graduate · Historical course

Spring 2004

Topics

  • Non-Bipartite Matching: Tutte-Berge Formula, Gallai-Edmonds Decomposition, Blossoms
  • Non-Bipartite Matching: Edmonds’ Cardinality Algorithm and Proofs of Tutte-Berge Formulas and Gallai-Edmonds Decomposition
  • Cubic Graphs and Matchings, Factor-Critical Graphs, Ear Decompositions
  • The Matching Polytope, Total Dual Integrality, and Hilbert Bases
  • Total Dual Integrality, Totally Unimodularity
  • Posets and Dilworth Theorem
  • Partitioning Digraphs by Paths and Covering them by Cycles
  • Proof of the Bessy-Thomasse Result
  • Matroids: Defs, Dual, Minor, Representability
  • Matroids: Representability, Greedy Algorithm, Matroid Polytope
  • Matroid Intersection
  • Matroid Intersection, Matroid Union, Shannon Switching Game
  • Matroid Intersection Polytope, Matroid Union
  • Matroid Union, Packing and Covering with Spanning Trees, Strong Basis Exchange Properties
  • Matroid Matching: Examples, Complexity, Lovasz’s Minmax Relation for Linear Matroids
  • Jump Systems: Definitions, Examples, Operations, Optimization, and Membership
  • Jump Systems: Membership (cont.)
  • Graph Orientations, Directed Cuts (Lucchesi-Younger Theorem), Submodular Flows
  • Submodular Flows: Examples, Edmonds-Giles Theorem, Reduction to Matroid Intersection in Special Cases
  • Splitting Off
  • Proof of Splitting-Off
  • Multiflow and Disjoint Path Problems
  • The Okamura-Seymour Theorem and the Wagner-Weihe Linear-Time Algorithm

Readings

  • Schrijver, Alexander. Combinatorial Optimization: Polyhedra and Efficiency. New York, NY: Springer-Verlag, 2003. ISBN: 3540443894.
    Listed reading
  • The textbook is the 3-volume book, but we will be covering only some of the 83 chapters. This is a marvelous book with lots of results, references and concise proofs. I will assume familiarity with many basic results in combinatorial optimization.
    Listed reading
  • In addition to the plethora of references in Schrijver’s textbook, here are a few references related to what is covered in lecture. Additional pointers appear in the scribe notes.
    Listed reading
  • Lovász, L., and M. D. Plummer. Matching Theory. Vol. 29. Annals of Discrete Mathematics. Amsterdam: North-Holland Publishing Co., 1986. [The reference for everything related to matching.]
    Listed reading
  • Oxley, J. G. Matroid Theory. New York: Oxford University Press, 1992. [An in-depth discussion of matroid theory.]
    Listed reading
  • Welsh, D. J. A., P. D. Seymour, R. E. Bixby, and W. H. Cunningham. In The Handbook of Combinatorics. Vol. 1. Cambridge, MA: MIT Press, 1995, Chapters on Matroids.
    Listed reading
  • Fujishige, S. Submodular Functions and Optimization. Vol. 47. Annals of Discrete Mathematics. Amsterdam: North-Holland Publishing Co., 1999.
    Listed reading
  • Bessy, S. “Stabilite et decomposition en circuits d’un digraphe.” In Dissertation. Universite Lyon I, 2003. [Lectures 7 and 8]
    Listed reading
  • Cunningham, W. H. “Matching, Matroid, and Extensions.” Mathematical Programming B91 (2002): 515-542. [Lectures 16 and 17]
    Listed reading
  • Lovász, L. “ The Membership Problem in Jump Systems .” J. Comb. Theory (B) 70: 45-66. [Lectures 16 and 17] ↗
    Listed reading
  • Frank, A. “Packing Paths, Circuits, and Cuts.” In Paths, Flows and VLSI-Layout. Edited by B. Korte, L. Lovász, H. J. Proemel, and A. Schrijver. New York, NY: Springer-Verlag, 1990. [Lectures 22 and 23]
    Listed reading
  • Wagner, D., and K. Weihe. “A Linear-time Algorithm for Edge-disjoint Paths in Planar Graphs.” Combinatorica 15 (1995): 135-150. [Lecture 23]
    Listed reading
Sources