Czy wystarczy, aby ograniczenia programu liniowego były spełnione w oczekiwaniu?

W artykule Randomized Primal-Dual analiza RANKING dla Online Dwustronnego dopasowywania , udowadniając jednocześnie, że algorytm RANKING jest -konkurencyjne, autorzy pokazują, że dualność jest wykonalna w oczekiwaniu (patrz Lemat 3 na stronie 5). Moje pytanie brzmi: $\left(1 - \frac{1}{e}\right)$

Czy wystarczy, aby ograniczenia programu liniowego były spełnione w oczekiwaniu?

Jedną rzeczą jest wykazanie, że oczekiwana wartość funkcji celu jest czymś. Ale jeśli ograniczenia wykonalności zostaną spełnione w oczekiwaniu, nie ma gwarancji, że zostaną spełnione w danym przebiegu. Ponadto istnieje wiele takich ograniczeń. Więc jaka jest gwarancja, że WSZYSTKO z nich zostaną spełnione w danym przebiegu?

linear-programming randomized-algorithms online-algorithms matching primal-dual Arindam Pal
źródło

Pomocne może być przeczytanie krótkiego postu na blogu Claire Mathieu na temat tej analizy. Kluczowe zdanie brzmi: „Dowodzi to wykonalności średniej liczby podwójnej”. (Podwójne rozwiązanie, którego naprawdę używasz, i które jest wykonalne, jest średnią z analiz dualnych w analizie.)

Neal Young,

zwróć uwagę, że odpowiedź na twoje pytanie brzmi również tak, w tym sensie, że jeśli ograniczenia liniowe są spełnione w oczekiwaniu, wówczas rozwiązanie podane przez przypisanie każdej zmiennej jej oczekiwanej wartości jest wykonalne (i ma koszt równy kosztowi oczekiwanemu). cuda liniowości oczekiwań;)

Sasho Nikolov,

Dzięki usul, Neal i Sasho za wyjaśnienie tej subtelnej kwestii.

Arindam Pal

Odpowiedzi:

Myślę, że trudność polega na tym, że to sformułowanie jest nieco mylące; jak podkreślono jaśniej we wstępie (1.2), „oczekiwane wartości zmiennych podwójnych stanowią możliwe podwójne rozwiązanie”.

Dla każdego ustalonego ustawienia zmiennych podwójnych uzyskujemy pewne pierwotne rozwiązanie wartości i podwójne rozwiązanie wartości $X$ $f(X)$ $\frac{e}{e-1}f(X)$

$E[f(X)]$ $E[X]$ $\frac{e}{e-1}f(E[X])$ $f(X)$ $X$ $\alpha_i$ $\beta_j$ $i$ $j$ $\left(\frac{e-1}{e}\right)(\alpha_i + \beta_j)$ do pierwotnego celu. Więc $E[f(X)] = f(E[X])$ i wniosek jest następujący.

(Na marginesie uważam, że ponieważ ten punkt jest jednym z głównych tematów ich pracy (zgodnie ze streszczeniem), byłoby lepiej, gdyby wyjaśnili ten punkt! To wcale nie wydaje się oczywiste ja i chciałbym dowiedzieć się, kiedy to jest bardziej ogólnie.)

usul
źródło

bardzo ładna odpowiedź.

Suresh Venkat,