Primal-Dual Algorithm

This post discusses the assignment problem, its primal-dual interpretation, and the gated Hungarian algorithm. Tutor HungarianAlgorithm and [4] gives a nice interpretation of the dual-prime of the Hungarian algorithm. Prime-Dual Interpretation of Hungarian Algorithm The following linear program gives a lower bound on the optimal value of the assignment problem: $$\begin{array}{ll} \min & \sum_{i \in I} \sum_{j \in J} c_{i j} x_{i j} \\ \text { s.t. } & \sum_{j \in J} x_{i j}=1 \text { for all } i \in I \\ & \sum_{i \in I} x_{i j}=1 \text { for all } j \in J \\ & x_{i j} \geq 0 \end{array}$$To see this, note that we can let $x_{i j}=1$ if $i$ is assigned to $j$ and 0 otherwise. Clearly, this is a feasible solution to the L.P, so the optimal value of the LP must be at most the optimal value of the assignment problem. ...