¿Es suficiente que las restricciones lineales del programa se cumplan en la expectativa?

En el artículo Análisis aleatorio Primal-Dual de RANKING para emparejamiento bipartito en línea , al tiempo que demuestra que el algoritmo RANKING es $\left(1 - \frac{1}{e}\right)$ -competitivo, los autores muestran que la dualidad es factible en expectativa (ver Lema 3 en la página 5). Mi pregunta es:

¿Es suficiente que las restricciones lineales del programa se cumplan en la expectativa?

Una cosa es mostrar que el valor esperado de la función objetivo es algo. Pero si las restricciones de viabilidad se satisfacen en la expectativa, no hay garantía de que se cumpla en una carrera determinada. Además, existen muchas limitaciones de este tipo. Entonces, ¿cuál es la garantía de que TODOS estarán satisfechos en una carrera determinada?

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

Puede que le resulte útil leer la breve publicación de blog de Claire Mathieu sobre este análisis. La oración clave es "Esto demuestra la viabilidad del promedio de los duales". (La solución dual que realmente usa, y que es factible, es el promedio de los duales en el análisis.)

Neal Young

tenga en cuenta que la respuesta a su pregunta también es sí en general, en el sentido de que si las restricciones lineales se satisfacen en la expectativa, entonces la solución dada al asignar a cada variable su valor esperado es factible (y tiene un costo igual al costo esperado). las maravillas de la linealidad de la expectativa;)

Sasho Nikolov

Gracias usul, Neal y Sasho por aclarar este punto sutil.

Arindam Pal

Respuestas:

Creo que la dificultad es que esta redacción es ligeramente engañosa; Como afirman más claramente en la Introducción (1.2), "los valores esperados de las variables duales constituyen una solución dual factible".

Para cada configuración fija de las variables duales , obtenemos alguna solución primaria de valor y una solución dual de valor $X$ $f(X)$ . (El dual es inviable en algunos de estos casos, pero está bien). $\frac{e}{e-1}f(X)$

Por lo tanto, el valor esperado de primal en todas las ejecuciones del algoritmo es . Pero es una solución dual factible, por lo que existe una solución dual de valor $E[f(X)]$ $E[X]$ . El truco clave es quees lineal en las variables duales: de hecho, aquí las variables duales sony, y cada coincidencia de vérticeasuma un total de $\frac{e}{e-1}f(E[X])$ $f(X)$ $X$ $\alpha_i$ $\beta_j$ $i$ $j$ al objetivo primario. Entoncesy la conclusión sigue. $\left(\frac{e-1}{e}\right)(\alpha_i + \beta_j)$ $E[f(X)] = f(E[X])$

(Como nota al margen, creo que, dado que este punto es uno de los principales focos de su trabajo (según el resumen), ¡hubiera sido mejor si hubieran explicado este punto! ¡No parece del todo obvio para yo, y me gustaría saber cuándo es más cierto en general).

usul
fuente

Muy buena respuesta.

Suresh Venkat