<p>I think the difficulty is that this wording slightly misleading; as they state more clearly in the Introduction (1.2), "the expected values of the dual variables constitute a feasible dual solution."</p>

<p>For every fixed setting of the dual variables $X$, we obtain some primal solution of value $f(X)$ and a dual solution of value $\frac{e}{e-1}f(X)$. (The dual is infeasible in some of these cases, but that's fine.)</p>

<p>So the expected value of the primal over all runs of the algorithm is $E[f(X)]$. But $E[X]$ is a dual-feasible solution, so there exists a dual solution of value $\frac{e}{e-1}f(E[X])$. The key trick is that $f(X)$ is linear in the dual variables $X$: In fact, here the dual variables are $\alpha_i$ and $\beta_j$, and each matching of vertex $i$ to $j$ adds a total of $\left(\frac{e-1}{e}\right)(\alpha_i + \beta_j)$ to the primal objective. So $E[f(X)] = f(E[X])$ and the conclusion follows.</p>

<p>(As a side note, I feel that, as this point is one of the main focuses of their paper (according to the abstract), it would have been nicer if they had explained this point! It doesn't seem at all obvious to me, and I would like to find out when it's true more generally.)</p>

CC BY-SA 3.0
2012-12-10T08:06:15.067Z
very nice answer.
Suresh Venkat
CC BY-SA 3.0
2012-12-10T06:16:41.350Z
2012-12-10T15:11:35.033Z
2012-12-10T15:11:35.033Z
usul
<p>In the paper <a href="http://www.cs.cornell.edu/courses/CS6820/2012fa/handouts/djk.pdf">Randomized Primal-Dual analysis of RANKING for Online Bipartite Matching</a>, while proving that the RANKING algorithm is $\left(1 - \frac{1}{e}\right)$-competitive, the authors show that the dual is feasible in expectation (see Lemma 3 on page 5). My question is:</p>

<blockquote>
  <p>Is it enough for linear program constraints to be satisfied in expectation?</p>
</blockquote>

<p>It is one thing to show that the expected value of the objective function is something. But if feasibility constraints are satisfied in expectation, there is no guarantee that it will be satisfied on a given run. Moreover, there are many such constraints. So what is the guarantee that <strong>ALL</strong> of them will be satisfied on a given run?</p>

CC BY-SA 3.0
2012-12-10T17:22:35.293Z
You might find it helpful to read [Claire Mathieu's brief blog post](http://teachingintrotocs.blogspot.com/2011/06/primal-dual-analysis-of-ranking.html) about this analysis.  The key sentence is *"This proves feasibility of the average of the duals."*  (The dual solution that you really use, and that is feasible, is the *average* of the duals in the analysis.)
Neal Young
CC BY-SA 3.0
2012-12-10T20:27:19.747Z
note that the answer to your question is yes in general as well, in the sense that if linear constraints are satisfied in expectation, then the solution given by assigning each variable its expected value is feasible (and has cost equal to the expected cost). the wonders of linearity of expectation ;)
Sasho Nikolov
CC BY-SA 3.0
2012-12-11T02:07:49.503Z
Thanks usul, Neal and Sasho for clarifying this subtle point.
Arindam Pal
<linear-programming><randomized-algorithms><online-algorithms><matching><primal-dual>
Is it enough for linear program constraints to be satisfied in expectation?
Arindam Pal
# Is it enough for linear program constraints to be satisfied in expectation?

(Asked by: username_0 on 2012-12-10)

In the paper [Randomized Primal-Dual analysis of RANKING for Online Bipartite Matching](http://www.cs.cornell.edu/courses/CS6820/2012fa/handouts/djk.pdf), while proving that the RANKING algorithm is $\left(1 - \frac{1}{e}\right)$-competitive, the authors show that the dual is feasible in expectation (see Lemma 3 on page 5). My question is:

> Is it enough for linear program constraints to be satisfied in expectation?

It is one thing to show that the expected value of the objective function is something. But if feasibility constraints are satisfied in expectation, there is no guarantee that it will be satisfied on a given run. Moreover, there are many such constraints. So what is the guarantee that **ALL** of them will be satisfied on a given run?

**Tags:** linear-programming, randomized-algorithms, online-algorithms, matching, primal-dual

> **Comments:**
> **username_1**: You might find it helpful to read [Claire Mathieu's brief blog post](http://teachingintrotocs.blogspot.com/2011/06/primal-dual-analysis-of-ranking.html) about this analysis.  The key sentence is *"This proves feasibility of the average of the duals."*  (The dual solution that you really use, and that is feasible, is the *average* of the duals in the analysis.)  
> **username_2**: note that the answer to your question is yes in general as well, in the sense that if linear constraints are satisfied in expectation, then the solution given by assigning each variable its expected value is feasible (and has cost equal to the expected cost). the wonders of linearity of expectation ;)  
> **username_0**: Thanks username_3, Neal and Sasho for clarifying this subtle point.  

---

## 1 answers

### Answer by username_3 on 2012-12-10. Score: 19 | Accepted answer

I think the difficulty is that this wording slightly misleading; as they state more clearly in the Introduction (1.2), "the expected values of the dual variables constitute a feasible dual solution."

For every fixed setting of the dual variables $X$, we obtain some primal solution of value $f(X)$ and a dual solution of value $\frac{e}{e-1}f(X)$. (The dual is infeasible in some of these cases, but that's fine.)

So the expected value of the primal over all runs of the algorithm is $E[f(X)]$. But $E[X]$ is a dual-feasible solution, so there exists a dual solution of value $\frac{e}{e-1}f(E[X])$. The key trick is that $f(X)$ is linear in the dual variables $X$: In fact, here the dual variables are $\alpha\_i$ and $\beta\_j$, and each matching of vertex $i$ to $j$ adds a total of $\left(\frac{e-1}{e}\right)(\alpha\_i + \beta\_j)$ to the primal objective. So $E[f(X)] = f(E[X])$ and the conclusion follows.

(As a side note, I feel that, as this point is one of the main focuses of their paper (according to the abstract), it would have been nicer if they had explained this point! It doesn't seem at all obvious to me, and I would like to find out when it's true more generally.)

> **Comments:**
> **username_4**: very nice answer.  

---

