Courses:

Topics in Combinatorial Optimization >> Content Detail



Lecture Notes



Lecture Notes

The lecture notes were scribed by students who took this class and are used with their permission.

LEC #TOPICSLECTURE NOTES
1Non-Bipartite Matching: Tutte-Berge Formula, Gallai-Edmonds Decomposition, Blossoms(PDF) by Nick Harvey (Courtesy of Nicholas Harvey. Used with permission.)
2Non-Bipartite Matching: Edmonds' Cardinality Algorithm and Proofs of Tutte-Berge Formulas and Gallai-Edmonds Decomposition(PDF) by Robert Kleinberg (Courtesy of Robert Kleinberg. Used with permission.)
3Cubic Graphs and Matchings, Factor-Critical Graphs, Ear Decompositions(PDF) by Dan Stratila (Courtesy of Dan Stratila. Used with permission.)
4The Matching Polytope, Total Dual Integrality, and Hilbert Bases(PDF) by Constantine Caramanis
5Total Dual Integrality, Totally Unimodularity

Matching Polytope and the Cunningham-Marsh Formula Showing TDI
(PDF) by Ben Recht (Courtesy of Benjamin Recht. Used with permission.)
6Posets and Dilworth Theorem

Deduce Konig's Theorem for Bipartite Matchings

Weighted Posets and the Chain and Antichain Polytopes
(PDF) by Joungkeun Lim (Courtesy of Joungkeun Lim. Used with permission.)
7Partitioning Digraphs by Paths and Covering them by Cycles

Gallai-Milgram and Bessy-Thomasse Theorems

Cyclic Orderings
(PDF) by Jan Vondrák (Courtesy of Jan Vondrák. Used with permission.)
8Proof of the Bessy-Thomasse Result

The Cyclic Stable Set Polytope
(PDF) by Constantine Caramanis (Courtesy of Constantine Caramanis. Used with permission.)
9Matroids: Defs, Dual, Minor, Representability(PDF) by Bridget Eileen Tenner (Courtesy of Bridget Tenner. Used with permission.)
10Matroids: Representability, Greedy Algorithm, Matroid Polytope(PDF) by Nicole Immorlica (Courtesy of Nicole Immorlica. Used with permission.)
11Matroid Intersection(PDF) by Fumei Lam (Courtesy of Fumei Lam. Used with permission.)
12Matroid Intersection, Matroid Union, Shannon Switching Game(PDF) by Vahab S. Mirrokni (Courtesy of Vahab Mirrokni. Used with permission.)
13Matroid Intersection Polytope, Matroid Union(PDF) by Constantine Caramanis (Courtesy of Constantine Caramanis. Used with permission.)
14Matroid Union, Packing and Covering with Spanning Trees, Strong Basis Exchange Properties(PDF) by Mohamed Mostagir (Courtesy of Mohamed Mostagir. Used with permission.)
15Matroid Matching: Examples, Complexity, Lovasz's Minmax Relation for Linear Matroids(PDF) by Supratim Deb (Courtesy of Supratim Deb. Used with permission.)
16Jump Systems: Definitions, Examples, Operations, Optimization, and Membership(PDF) by Jonathan Kelner (Courtesy of Jonathan Kelner. Used with permission.)
17Jump Systems: Membership (cont.)
18Graph Orientations, Directed Cuts (Lucchesi-Younger Theorem), Submodular Flows(PDF) by Nick Harvey (Courtesy of Nicholas Harvey. Used with permission.)
19Submodular Flows: Examples, Edmonds-Giles Theorem, Reduction to Matroid Intersection in Special Cases(PDF) by Ben Recht (Courtesy of Benjamin Recht. Used with permission.)
20Splitting Off

$k$-Connectivity Orientations and Augmentations
(PDF) by Jan Vondrák (Courtesy of Jan Vondrák. Used with permission.)
21Proof of Splitting-Off

Submodular Function Minimization
(PDF) by Mohamed Mostagir (Courtesy of Mohamed Mostagir. Used with permission.)
22Multiflow and Disjoint Path Problems

Two-Commodity Flows
(PDF) by Alantha Newman (Courtesy of Nicholas Harvey. Used with permission.)
23The Okamura-Seymour Theorem

The Wagner-Weihe Algorithm
(PDF) by Dan Stratila

 








© 2009-2020 HigherEdSpace.com, All Rights Reserved.
Higher Ed Space ® is a registered trademark of AmeriCareers LLC.