É suficiente que as restrições lineares do programa sejam satisfeitas nas expectativas?

No artigo Análise Primal-Dupla Aleatória de RANKING para Correspondência Bipartida Online , ao provar que o algoritmo RANKING é competitivos, os autores mostram que o dual é viável em expectativa (ver Lema 3 na página 5). Minha pergunta é: $\left(1 - \frac{1}{e}\right)$

É suficiente que as restrições lineares do programa sejam satisfeitas nas expectativas?

Uma coisa é mostrar que o valor esperado da função objetivo é alguma coisa. Mas se as restrições de viabilidade forem atendidas na expectativa, não há garantia de que serão atendidas em uma determinada execução. Além disso, existem muitas dessas restrições. Então, qual é a garantia de que TODOS eles serão satisfeitos em uma determinada execução?

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

Talvez seja útil ler a breve publicação de Claire Mathieu no blog sobre essa análise. A frase-chave é "Isso prova a viabilidade da média dos duplos". (A solução dupla que você realmente usar, e que é viável, é a média dos duos na análise.)

Neal Young

observe que a resposta para sua pergunta também é sim em geral, no sentido de que, se as restrições lineares forem satisfeitas na expectativa, a solução dada ao atribuir a cada variável seu valor esperado é viável (e tem custo igual ao custo esperado). as maravilhas da linearidade da expectativa;)

Sasho Nikolov

Obrigado usul, Neal e Sasho por esclarecer esse ponto sutil.

Arindam Pal

Respostas:

Eu acho que a dificuldade é que essa redação é um pouco enganadora; como afirmam mais claramente na Introdução (1.2), "os valores esperados das variáveis duplas constituem uma solução dupla viável".

Para cada configuração fixa das variáveis duplas , obtemos uma solução primária do valor e uma solução dupla do valor $X$ $f(X)$ $\frac{e}{e-1}f(X)$ . (O dual é inviável em alguns desses casos, mas tudo bem.)

Portanto, o valor esperado do primal em todas as execuções do algoritmo é . Mas é uma solução viável dupla, então existe uma solução dupla de valor $E[f(X)]$ $E[X]$ . O truque principal é queé linear nas variáveis duplas: De fato, aqui as variáveis duplas sãoe, e cada correspondência dos vérticesaadiciona um total de $\frac{e}{e-1}f(E[X])$ $f(X)$ $X$ $\alpha_i$ $\beta_j$ $i$ $j$ para o objectivo primordial. Entãoe a conclusão a seguir. $\left(\frac{e-1}{e}\right)(\alpha_i + \beta_j)$ $E[f(X)] = f(E[X])$

(Como uma observação lateral, eu sinto que, como esse ponto é um dos principais focos de seu artigo (de acordo com o resumo), teria sido melhor se eles tivessem explicado esse ponto! eu e gostaria de descobrir quando isso é verdade de maneira mais geral.)

usul
fonte

resposta muito boa.

Suresh Venkat