MIT OpenCourseWare

Browse materialsMIT 18.997 · Spring 2004

Topics in Combinatorial Optimization

Art: Anonymous painter,15th century, Westerner and Arab practicing geometry 15th century manuscript, 15th… · Public domain

Instructor: Prof. Michel Goemans
Term: Spring 2004
Level: Graduate
What's inside: 1 lecture note · 1 reading · 22 other files · 3 web pages
Materials open: MIT OCW

Start here

Start course: Lecture 1: Non-Bipartite Matching: Tutte-Berge Formula…Find a topic

Progress is saved in this browser.

Export or import progress

About this course

Source: MIT OpenCourseWare 18.997 Topics in Combinatorial Optimization, Spring 2004, Prof. Michel Goemans — original course page on ocw.mit.edu ↗. License: CC BY-NC-SA 4.0. Study order: MIT's own listing order, section by section. Taken from MIT's published course files, downloaded from ocw.mit.edu on September 23, 2026. How RedLectern is built.

Materials are grouped the way MIT organized them. A verified, course-wide order has not been established here.

Before you start

Prerequisites are not listed here. Check MIT's own syllabus for this course.

How this course was organized

What's here, and what isn't

A lecture sequence of 23 items is confirmed. It stays as organized materials rather than a full course order.

Not included here

1 item from the source could not be safely included:

MIT's page format for this item wasn't recognized clearly enough to place it safely.

Materials by section

Grouped by section, as MIT organized them. Not sequenced or ordered.

Lecture Notes

22 files

MIT OpenCourseWare, Prof. Michel Goemans, 18.997 Topics in Combinatorial Optimization, Spring 2004.

License: CC BY-NC-SA 4.0 · Edition: Spring 2004 · Open the original course on OCW ↗

Organized by RedLectern, independent of MIT and not endorsed by MIT.

Per-resource rights are recorded on each resource; All-Rights-Reserved items are link-only, never mirrored.

Topics in Combinatorial Optimization

Before you start

What's here, and what isn't

Not included here

Materials by section

Lecture Notes

Lecture 1: Non-Bipartite Matching: Tutte-Berge Formula, Gallai-Edmonds Decomposition, Blossoms

Lecture 2: Non-Bipartite Matching: Edmonds’ Cardinality Algorithm and Proofs of Tutte-Berge Formulas and Gallai-Edmonds Decomposition

Lecture 3: Cubic Graphs and Matchings, Factor-Critical Graphs, Ear Decompositions

Lecture 4: The Matching Polytope, Total Dual Integrality, and Hilbert Bases

Lecture 5: Total Dual Integrality, Totally Unimodularity Matching Polytope and the Cunningham-Marsh Formula Showing TDI

Lecture 6: Posets and Dilworth Theorem Deduce Konig’s Theorem for Bipartite Matchings Weighted Posets and the Chain and Antichain Polytopes

Lecture 7: Partitioning Digraphs by Paths and Covering them by Cycles Gallai-Milgram and Bessy-Thomasse Theorems Cyclic Orderings

Lecture 8: Proof of the Bessy-Thomasse Result The Cyclic Stable Set Polytope

Lecture 9: Matroids: Defs, Dual, Minor, Representability

Lecture 10: Matroids: Representability, Greedy Algorithm, Matroid Polytope

Lecture 11: Matroid Intersection

Lecture 12: Matroid Intersection, Matroid Union, Shannon Switching Game

Lecture 13: Matroid Intersection Polytope, Matroid Union

Lecture 14: Matroid Union, Packing and Covering with Spanning Trees, Strong Basis Exchange Properties

Lecture 15: Matroid Matching: Examples, Complexity, Lovasz’s Minmax Relation for Linear Matroids

Lecture 16: Jump Systems: Definitions, Examples, Operations, Optimization, and Membership

Lecture 17: Jump Systems: Membership (cont.)

Lecture 18: Graph Orientations, Directed Cuts (Lucchesi-Younger Theorem), Submodular Flows

Lecture 19: Submodular Flows: Examples, Edmonds-Giles Theorem, Reduction to Matroid Intersection in Special Cases

Lecture 20: Splitting Off $k$-Connectivity Orientations and Augmentations

Lecture 21: Proof of Splitting-Off Submodular Function Minimization

Lecture 22: Multiflow and Disjoint Path Problems Two-Commodity Flows

Lecture 23: The Okamura-Seymour Theorem and the Wagner-Weihe Linear-Time Algorithm