LP&CO 2026 Lecture-33: Minimum Cost Perfect Matching (bipartite) --- towards a primal-dual algorithm
Nishad-Kothari-IIT-Madras · 50:43 · Watch on YouTube
The lecture develops a primal-dual algorithm for minimum-cost perfect matching in a bipartite graph: keep a feasible vertex labeling, restrict attention to tight edges, and whenever that tight graph has no perfect mat...