14
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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.) $\endgroup$
    – Neal Young
    Dec 10 '12 at 17:22
  • 1
    $\begingroup$ 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 ;) $\endgroup$
    – Sasho Nikolov
    Dec 10 '12 at 20:27
  • $\begingroup$ Thanks usul, Neal and Sasho for clarifying this subtle point. $\endgroup$
    – Arindam Pal
    Dec 11 '12 at 2:07
19
$\begingroup$

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.)

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ very nice answer. $\endgroup$
    – Suresh Venkat
    Dec 10 '12 at 8:06

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.