Скачать или смотреть Linear Programming & Combinatorial Optimization (2022) Lecture-32

In today's lecture (24/03/2022), we used the CS conditions (discussed yesterday) to design a primal-dual algorithm for the Min Cost Perfect Matching (PM) problem for Bipartite Graphs. The process/intuition we followed was quite similar to what we did for the Shortest Path Problem.

At each step (of the primal-dual algorithm), we've a Dual Feasible Solution (DFS) y*, and using this we construct a tight graph H --- which has only those edges that are tight (with respect to y*). If the tight graph H has a PM, say M, then the algorithm returns M, y*. Otherwise, the algorithm uses a deficient set S (in H) to improve the DFS in a systematic manner. (The initial DFS is easy to construct.)

Today, we focused on an example, and the intuition behind designing the algorithm. Tomorrow (25/03), we will formalize the algorithm and analyze its time-complexity (i.e., running time).