Why is complementary slackness important?

Question

Complementary slackness (CS) is commonly taught when talking about duality. It establishes a nice relation between the primal and the dual constraint/variables from a mathematical viewpoint.

The two primary reasons for applying CS (as taught in graduate courses and textbooks):

1. To check the optimality of the LP
2. To help solve the dual

Given today's computing power and polynomial algorithms for solving LPs is CS still relevant from a pragmatic viewpoint? We could always just solve the duals and address both the points above. I agree that it's "more efficient" to solve the dual with the help of CS but is that it? Or is there more to CS than meets the eye? Where exactly is CS useful beyond the above two points? I've commonly seen texts alluding to the concept of CS when talking about approximation algorithms but I fail to understand its role there.

Answer 1

Complementary slackness is key in designing primal-dual algorithms. The basic idea is:

1. Start with a feasible dual solution $y$.
2. Attempt to find primal feasible $x$ such that $(x, y)$ satisfy complementary slackness.
3. 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.