<p>Complementary slackness is key in designing primal-dual algorithms. The basic idea is:</p>

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

<p>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. <strong>This is the power of complementary slackness.</strong> 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$.</p>

<p>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.</p>

<p>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 <a href="http://www.designofapproxalgs.com/" rel="noreferrer">Williamson-Shmoys book</a>) and in designing online algorithms with good competitive ratio (see the <a href="http://www.tau.ac.il/~nivb/download/pd-survey.pdf" rel="noreferrer">book by Buchbinder and Naor</a>). 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 <em>integral</em> primal feasible $x$ such that <em>approximate</em> complementary slackness is satisfied, or improves the dual solution $y$. Approximate complementary slackness is a condition of the following form: if $x_i &gt; 0$ then the corresponding dual constraint is tight, and if $y_j &gt; 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.</p>

CC BY-SA 3.0
2014-06-15T11:07:05.793Z
2014-06-16T21:48:38.093Z
2014-06-16T21:48:38.093Z
Sasho Nikolov
<p>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.</p>

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

<ol>
<li>To check the optimality of the LP</li>
<li>To help solve the dual</li>
</ol>

<p>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? <em>Where exactly is CS useful beyond the above two points</em>? I've commonly seen texts alluding to the concept of CS when talking about approximation algorithms but I fail to understand its role there.</p>

CC BY-SA 3.0
2014-06-13T18:07:08.543Z
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?
Robin Kothari
CC BY-SA 3.0
2014-06-13T18:36:42.170Z
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.
PhD
CC BY-SA 3.0
2014-06-14T04:56:58.463Z
Well, I think it can help with getting "analytic" solutions ... that might be more difficult to get with a computer.
usul
CC BY-SA 3.0
2014-06-15T14:24:09.463Z
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?
Chandra Chekuri
CC BY-SA 3.0
2014-06-15T20:00:18.703Z
@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
PhD
<ds.algorithms><approximation-algorithms><linear-programming><primal-dual>
Why is complementary slackness important?
PhD
# Why is complementary slackness important?

(Asked by: username_0 on 2014-06-13)

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.

**Tags:** ds.algorithms, approximation-algorithms, linear-programming, primal-dual
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.  
> **username_2**: Well, I think it can help with getting "analytic" solutions ... that might be more difficult to get with a computer.  
> **username_3**: 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?  
> **username_0**: @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  

---

## 1 answers

### Answer by username_4 on 2014-06-15. Score: 14 | Accepted answer

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](http://www.designofapproxalgs.com/)) and in designing online algorithms with good competitive ratio (see the [book by Buchbinder and Naor](http://www.tau.ac.il/~nivb/download/pd-survey.pdf)). 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.


---

