Linear Programming & Combinatorial Optimization (2022) Lecture-27

In today's lecture, we commenced Module-5 (Primal-Dual Algorithms) --- where (almost) everything (we've studied so far) comes together.

In particular, our first primal-dual algorithm is for the Shortest st-path Problem. We wrote down the ILP (P'), its LP relaxation (P) and its dual (D), and we wrote down combinatorial interpretations: (i) of the dual (D), (ii) of Weak duality and of (iii) Complementary Slackness conditions.

Our key observation may be summarized as follows:
If Q is an st-path and y* is a dual feasible solution that satisfy the following CS conditions:
(1) if the dual variable corresponding to an st-cut F is greater than zero then F meets Q in precisely one edge, and
(2) if an edge e belongs to the path Q then (the summation of all of the dual variables corresponding to cuts containing edge e) must equal the cost of edge e,
then Q is a shortest st-path (and y* is an optimal solution to (D)).

These conditions (1) and (2) will be the guiding principles behind the primal-dual algorithm that we are about to see in the next 1 or 2 lectures. In the first step (towards designing our algorithm), we'll focus on condition (2). Thereafter, we'll address condition (1) using an additional trick.

We continue this discussion on 16/03/2022.