18.433
Combinatorial Optimization
Fall 2003
Topics
- Course Introduction
- The Hungarian Algorithm
- Edmonds’ Algorithm
- Polyhedral Combinatorics
- The Matching Polytope I
- The Matching Polytope II
- Flow Theory and Duality
- Max-flow Algorithms
- Min-cut Algorithms
- Min-cost Flow
- Strongly Polynomial Algorithms
- Linear Programming Duality
- The Simplex Algorithm
- The Simplex Algorithm (contd.)
- Complementary Slackness
- The Ellipsoid Algorithm I: Ideas
- The Ellipsoid Algorithm II: Details
- Separation Oracles I: Convex Problems
- Oracles II: Combinatorial Problems
- NP-completeness
- Approximation Algorithms
- The Relax-and-round Paradigm
- Projects Reviews
Readings
- Lovasz, Laszlo. Matching Theory .
- Ahuja, R., T. Magnanti, and J. Orlin. Network Flows .
- Schrijver, A. Theory of Linear and Integer Programming .
- Chvatal, V. Linear Programming .
- Bertsimas, D., and J. Tsitsiklis. Linear Optimization.
- Cook, W. J., W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver. Combinatorial Optimization .
- Papadimitriou, C. H., and K. Steiglitz. Combinatorial Optimization .
Sources
- Course catalogue ↗Historical OpenCourseWare
- MIT OCW calendar ↗
- MIT OCW readings ↗
- MIT OCW syllabus ↗
- Historical MIT OpenCourseWare offering. Named reading entries and schedule topics are automatically extracted from the linked source pages.