In this graduate-level course, we will be covering advanced topics in combinatorial optimization
September 23, 2022
English
English [CC]
Description
We will start with non-bipartite matchings and cover many results extending the fundamental results of matchings, flows and matroids. The emphasis is on the derivation of purely combinatorial results, including min-max relations, and not so much on the corresponding algorithmic questions of how to find such objects. The intended audience consists of Ph.D. students interested in optimization, combinatorics, or combinatorial algorithms.
Course Curriculum
- Non-Bipartite Matching Unlimited
- Non-Bipartite Matching: Edmonds’ Cardinality Algorithm and Proofs of Tutte-Berge Formulas and Gallai-Edmonds Decomposition Unlimited
- Cubic Graphs and Matchings, Factor-Critical Graphs, Ear Decompositions Unlimited
- The Matching Polytope, Total Dual Integrality, and Hilbert Bases Unlimited
- Total Dual Integrality, Totally Unimodularity Unlimited
- Posets and Dilworth Theorem Unlimited
- Partitioning Digraphs by Paths and Covering them by Cycles Unlimited
- Proof of the Bessy-Thomasse Result The Cyclic Stable Set Polytope Unlimited
- Matroids: Defs, Dual, Minor, Representability Unlimited
- Matroids: Representability, Greedy Algorithm, Matroid Polytope Unlimited
- Matroid Intersection Unlimited
- Matroid Intersection, Matroid Union, Shannon Switching Game Unlimited
- Matroid Intersection Polytope, Matroid Union Unlimited
- Matroid Union Unlimited
- Matroid Matching Unlimited
- Jump Systems Unlimited
- Graph Orientations Unlimited
- Submodular Flows Unlimited
- Splitting Off Unlimited
- Proof of Splitting-Off Submodular Function Minimization Unlimited
- Multiflow and Disjoint Path Problems Two-Commodity Flows Unlimited
- The Okamura-Seymour Theorem The Wagner-Weihe Algorithm Unlimited
About the instructor
5
5
Instructor Rating
1
Reviews
1520
Courses
1916
Students
Massachusetts Institute of Technology
FREE
Hours of videos
Units & Quizzes
Unlimited Lifetime access
Access on mobile app
Certificate of Completion
- For teams of 2 or more users
- 27,000+ fresh & in-demand courses
- Learning Engagement tools
- SSO and LMS Integrations