Courses:

When you click the Amazon logo to the left of any citation and purchase the book (or other media) from Amazon.com, MIT OpenCourseWare will receive up to 10% of this purchase and any other purchases you make during that visit. This will not increase the cost of your purchase. Links provided are to the US Amazon site, but you can also support OCW through Amazon sites in other regions. Learn more.

Schrijver, Alexander. Combinatorial Optimization: Polyhedra and Efficiency. New York, NY: Springer-Verlag, 2003. ISBN: 3540443894.

Additional References

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.

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.]

Oxley, J. G. Matroid Theory. New York: Oxford University Press, 1992. [An in-depth discussion of matroid theory.]

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.

Fujishige, S. Submodular Functions and Optimization. Vol. 47. Annals of Discrete Mathematics. Amsterdam: North-Holland Publishing Co., 1999.

Bessy, S. "Stabilite et decomposition en circuits d'un digraphe." In Dissertation. Universite Lyon I, 2003. [Lectures 7 and 8]

Cunningham, W. H. "Matching, Matroid, and Extensions." Mathematical Programming B91 (2002): 515-542. [Lectures 16 and 17]

Lovász, L. "The Membership Problem in Jump Systems." J. Comb. Theory (B) 70: 45-66. [Lectures 16 and 17]

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]

Wagner, D., and K. Weihe. "A Linear-time Algorithm for Edge-disjoint Paths in Planar Graphs." Combinatorica 15 (1995): 135-150. [Lecture 23]