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

In the paper Randomized Primal-Dual analysis of RANKING for Online Bipartite Matching, 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?

• You might find it helpful to read Claire Mathieu's brief blog post 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.) Dec 10, 2012 at 17:22
• 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 ;) Dec 10, 2012 at 20:27
• Thanks usul, Neal and Sasho for clarifying this subtle point. Dec 11, 2012 at 2:07

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.