Reicht es aus, wenn lineare Programmeinschränkungen in der Erwartung erfüllt werden?

In der Arbeit Randomized Primal-Dual-Analyse von RANKING für Online Bipartite Matching zeigen die Autoren, dass der RANKING- Algorithmus -kompetitiv ist Erwartung (siehe Lemma 3 auf Seite 5). Meine Frage ist: $\left(1 - \frac{1}{e}\right)$

Reicht es aus, wenn lineare Programmeinschränkungen in der Erwartung erfüllt werden?

Es ist eine Sache zu zeigen, dass der erwartete Wert der Zielfunktion etwas ist. Wenn jedoch Machbarkeitsbeschränkungen in der Erwartung erfüllt werden, gibt es keine Garantie dafür, dass sie bei einem bestimmten Lauf erfüllt werden. Darüber hinaus gibt es viele solche Einschränkungen. Was ist die Garantie, dass ALLE von ihnen bei einem bestimmten Lauf zufrieden sind?

linear-programming randomized-algorithms online-algorithms matching primal-dual Arindam Pal
quelle

Vielleicht ist es hilfreich, den kurzen Blog-Beitrag von Claire Mathieu über diese Analyse zu lesen . Der Schlüsselsatz lautet: "Dies beweist die Machbarkeit des Durchschnitts der Dualen." (Die Dual-Lösung, die Sie wirklich verwenden, und die machbar ist, ist der Durchschnitt der Duals in der Analyse.)

Neal Young

Beachten Sie, dass die Antwort auf Ihre Frage auch im Allgemeinen Ja lautet, in dem Sinne, dass die durch Zuweisen des erwarteten Werts jeder Variablen gegebene Lösung durchführbar ist (und die Kosten den erwarteten Kosten entsprechen), wenn die linearen Bedingungen in der Erwartung erfüllt sind. die Wunder der Linearität der Erwartung;)

Sasho Nikolov

Vielen Dank an Usul, Neal und Sasho für die Klärung dieses subtilen Punktes.

Arindam Pal

Antworten:

Ich denke, die Schwierigkeit besteht darin, dass diese Formulierung leicht irreführend ist. Wie sie in der Einleitung (1.2) klarer ausdrücken, "stellen die erwarteten Werte der dualen Variablen eine praktikable duale Lösung dar".

Für jede feste Einstellung der Doppelvariablen erhalten wir eine Primärlösung des Wertes und eine Doppellösung des Wertes $X$ $f(X)$ . (Das Dual ist in einigen dieser Fälle nicht möglich, aber das ist in Ordnung.) $\frac{e}{e-1}f(X)$

Der erwartete Wert des Primals über alle Läufe des Algorithmus ist also . Aber ist eine duale Lösung, es gibt also eine duale Lösung mit dem Wert $E[f(X)]$ $E[X]$ . Der entscheidende Trick ist, dassin den dualen Variablenlinear ist: Tatsächlich sind hier die dualen Variablenund, und jede Übereinstimmung von Vertexmitaddiert eine Summe von $\frac{e}{e-1}f(E[X])$ $f(X)$ $X$ $\alpha_i$ $\beta_j$ $i$ $j$ zum Urziel. Also istund die Schlussfolgerung folgt. $\left(\frac{e-1}{e}\right)(\alpha_i + \beta_j)$ $E[f(X)] = f(E[X])$

(Als Randnotiz habe ich das Gefühl, dass es, da dieser Punkt einer der Hauptschwerpunkte ihrer Arbeit ist (der Zusammenfassung zufolge), schöner gewesen wäre, wenn sie diesen Punkt erklärt hätten! Es scheint überhaupt nicht offensichtlich zu sein und ich würde gerne herausfinden, wann es allgemeiner wahr ist.)

usul
quelle

sehr nette antwort.

Suresh Venkat