Complementary slackness is key in designing primal-dual algorithms. The basic idea is:
- Start with a feasible dual solution $y$.
- Attempt to find primal feasible $x$ such that $(x, y)$ satisfy complementary slackness.
- If step 2. succeeded we are done. Otherwise an obstruction to finding $x$ gives a way to modify $y$ so that the dual objective function value increases. Repeat.
A classical example is the Hungarian algorithm. The Ford-Fulkerson algorithm can be seen as another example. Note that step 2. is a feasibility problem which often is easier than the original optimization problem, and also often can be solved combinatorially. This is the power of complementary slackness. For example, in the case of minimum cost bipartite matching, step 2 amounts to checking if there exists a perfect matching
using only tight edges. In the case of maximum $s$-$t$ flow, step 2 amounts to checking if the saturated edges separate $s$ and $t$.
Primal-dual algorithms are nice for many reasons. Philosophically, they provide more insight than a generic algorithm. They usually give strongly polynomial time algorithms, whereas we still do not have strongly polynomial LP solvers. They are often more practical than generic algorithms. This is especially true if we cannot write down the LP explicitly and our only other choice is the ellipsoid algorithm, which is the case with non-bipartite matching and Edmonds' primal-dual algorithm.
Primal-dual is also a very useful framework for approximation algorithms, by using relaxed versions of complementary slackness. This has been useful in designing approximation algorithms for NP-hard problems (see e.g. Chapter 7 of the Williamson-Shmoys book) and in designing online algorithms with good competitive ratio (see the book by Buchbinder and Naor). The point here is that the algorithm maintains a solution $y$ to the dual of the LP relaxation of a hard problem, and at each step either finds an integral primal feasible $x$ such that approximate complementary slackness is satisfied, or improves the dual solution $y$. Approximate complementary slackness is a condition of the following form: if $x_i > 0$ then the corresponding dual constraint is tight, and if $y_j > 0$, the corresponding primal constraint would be tight if $x$ is scaled by $\alpha$. This gives an approximation factor $\alpha$. It's all very nicely explained in the above two sources.