Linear Programming & Combinatorial Optimization (2022) Lecture-29

In today's lecture (17/03/2022), we continued our discussion on the shortest path primal-dual algorithm.

In the last lecture, we had completed an intuitive treatment of the algorithm --- focusing on how one might pursue designing such a primal-dual algorithm (for the shortest path problem) --- and how complementary slackness conditions (and LP duality theory, in general) guide this pursuit.

Today, we formalized the algorithm that we designed yesterday, and wrote it down in the form of a pseudocode (as is generally done in the case of algorithms). In order to do so, we also discussed some basic terminology from Digraph (aka Directed Graph) Theory.

In particular, our algorithm maintained a dual feasible solution (DFS) at each step, and used this DFS to guide the search for a "better" DFS in a systematic fashion. At the final step, the algorithm returns both a shortest st-path Q (which is an optimal solution to primal LP --- the LP relaxation of the shortest path ILP) as well as an optimal DFS y* (which may be viewed as a certificate of optimality). Such algorithms are called primal-dual algorithms, and they appear abundantly in combinatorial optimization problems.

Next, we seek a primal-dual algorithm for the Minimum Cost Perfect Matching problem. In this case, however, the Bipartite version is significantly easier than the Nonbipartite aka General version (as is almost always the case in Matching Theory). Thus, we'll begin with the Bipartite version.

Tomorrow (18/03/2022), we will focus on finding a maximum matching (as well as a perfect matching) in a bipartite graph.