9
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Not my area of expertise, but it sounds like you're asking why we teach properties of X even though deciding X is computationally easy. E.g., why do we teach the "no odd cycles = bipartite" characterization of bipartiteness even though we have polynomial time algorithms for checking bipartiteness. Is that what you're asking, in some sense? $\endgroup$ – Robin Kothari Jun 13 '14 at 18:07
  • $\begingroup$ Not exactly. I understand "why" you teach it. I wish to know from a practical POV how is it used when solving LPs and/or designing approximation algorithms. What's the insight we get other than the mathematical relationships between the variables and constraints. $\endgroup$ – PhD Jun 13 '14 at 18:36
  • $\begingroup$ Well, I think it can help with getting "analytic" solutions ... that might be more difficult to get with a computer. $\endgroup$ – usul Jun 14 '14 at 4:56
  • 1
    $\begingroup$ I don't "get" the question. Just because we use calculators and computers to add and multiply numbers do we still need to know properties of numbers? $\endgroup$ – Chandra Chekuri Jun 15 '14 at 14:24
  • $\begingroup$ @ChandraChekuri - I don't mean that. I'm just trying to figure out what's so great about this theorem and what makes it important. I don't want to accept it as a "that is how it is" but would like to have a deeper understanding of its importance w.r.t. LP duality $\endgroup$ – PhD Jun 15 '14 at 20:00
13
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.