Достаточно ли, чтобы линейные программные ограничения были выполнены в ожидании?

В статье « Рандомизированный анализ ранга-двойственности RANKING для сопоставления двухчастных он- лайн , доказывая, что алгоритм RANKING является -конкурентоспособным, авторы показывают, что двойственное возможно в ожидание (см. лемму 3 на стр. 5). Мой вопрос:$\left(1 - \frac{1}{e}\right)$

Достаточно ли, чтобы линейные программные ограничения были выполнены в ожидании?

Одно дело показать, что ожидаемое значение целевой функции - это нечто. Но если технико-экономические ограничения в ожидании удовлетворяются, нет гарантии, что они будут выполнены на данном этапе. Более того, таких ограничений много. Так, какова гарантия, что ВСЕ из них будут удовлетворены на данном пробеге?

Я думаю, что трудность в том, что эта формулировка немного вводит в заблуждение; как они более четко заявили во введении (1.2), «ожидаемые значения двойственных переменных составляют выполнимое двойное решение».

Для каждой фиксированной установки двойственных переменных мы получаем некоторое первичное решение значения и двойственное решение значения . (Двойное невозможно в некоторых случаях, но это нормально.)$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)$$E[f(X)] = f(E[X])$

(Как примечание стороны, я чувствую, что, поскольку этот пункт является одним из основных направлений их работы (согласно аннотации), было бы лучше, если бы они объяснили этот пункт! я, и я хотел бы узнать, когда это правда в более общем плане.)