Suffit-il que les contraintes linéaires du programme soient satisfaites dans l'attente?

Dans l'article Randomized Primal-Dual analysis of RANKING for Online Bipartite Matching , tout en prouvant que l'algorithme RANKING est -concurrentiel, les auteurs montrent que le dual est réalisable en attente (voir Lemme 3 page 5). Ma question est: $\left(1 - \frac{1}{e}\right)$

Suffit-il que les contraintes linéaires du programme soient satisfaites dans l'attente?

C'est une chose de montrer que la valeur attendue de la fonction objectif est quelque chose. Mais si les contraintes de faisabilité sont satisfaites dans l'attente, il n'y a aucune garantie qu'elles seront satisfaites sur un cycle donné. De plus, il existe de nombreuses contraintes de ce type. Alors, quelle est la garantie que TOUS seront satisfaits sur une course donnée?

linear-programming randomized-algorithms online-algorithms matching primal-dual Arindam Pal
la source

Vous pourriez trouver utile de lire le bref billet de blog de Claire Mathieu sur cette analyse. La phrase clé est "Cela prouve la faisabilité de la moyenne des duels". (La double solution que vous utilisez vraiment, et qui est faisable, est la moyenne des duals dans l'analyse.)

Neal Young

notez que la réponse à votre question est également oui en général, dans le sens où si les contraintes linéaires sont satisfaites dans l'attente, alors la solution donnée en attribuant à chaque variable sa valeur attendue est faisable (et a un coût égal au coût attendu). les merveilles de la linéarité de l'attente;)

Sasho Nikolov

Merci usul, Neal et Sasho d'avoir clarifié ce point subtil.

Arindam Pal

Réponses:

Je pense que la difficulté est que cette formulation est légèrement trompeuse; comme ils le disent plus clairement dans l'introduction (1.2), "les valeurs attendues des variables doubles constituent une solution double réalisable".

Pour chaque réglage fixe des variables doubles , nous obtenons une solution primale de valeur et une solution double de valeur $X$ $f(X)$ . (Le double est impossible dans certains de ces cas, mais c'est très bien.) $\frac{e}{e-1}f(X)$

Ainsi, la valeur attendue de la primale sur toutes les exécutions de l'algorithme est . Mais est une solution à double faisabilité, il existe donc une solution double de valeur $E[f(X)]$ $E[X]$ . L'astuce clé est queest linéaire dans les variables doubles: En fait, ici les variables doubles sontet, et chaque correspondance du sommetàajoute un total de $\frac{e}{e-1}f(E[X])$ $f(X)$ $X$ $\alpha_i$ $\beta_j$ $i$ $j$ à l'objectif primaire. Donc $\left(\frac{e-1}{e}\right)(\alpha_i + \beta_j)$ $E[f(X)] = f(E[X])$ et la conclusion suit.

(En remarque, je pense que, comme ce point est l'un des principaux axes de leur article (selon le résumé), il aurait été plus agréable qu'ils aient expliqué ce point! Il ne semble pas du tout évident de moi, et je voudrais savoir quand c'est vrai plus généralement.)

usul
la source

très belle réponse.

Suresh Venkat