Intervalo de integralidade e razão de aproximação

Quando consideramos um algoritmo de aproximação para um problema de minimização, o gap de integralidade de uma formulação IP para esse problema fornece um limite inferior de uma taxa de aproximação para determinada classe de algoritmos (como arredondamento ou algoritmo primal-duplo). De fato, existem muitos problemas cuja melhor taxa de aproximação corresponde à diferença de integralidade.

Algum algoritmo pode ter uma taxa de aproximação melhor do que a diferença de integralidade para algum problema, mas não sei se esse exemplo existe ou não. Se a resposta for sim, você poderia dar alguns exemplos?

Eu sei que alguns problemas admitem múltiplas formulações matemáticas. Nesses casos, considere a formulação matemática com o menor intervalo de integralidade, desde que possa ser resolvida em tempo polinomial (talvez algumas formulações possam usar oráculos de separação).

Esta questão está relacionada à [a questão: A importância da abertura da integralidade] .

ds.algorithms approximation-algorithms linear-programming integrality-gap Snowie
fonte

Eu acho que o TSP geométrico seria um exemplo de um problema desse tipo, mas não tenho nenhuma referência.

Jukka Suomela

E quanto aos problemas que admitem um PTAS usando a estratégia de mudança? Algum deles possui uma formulação de PI com uma diferença de integridade arbitrariamente pequena?

Jukka Suomela

O TSP geométrico da Jukka é um bom exemplo. O exemplo de gap de integralidade 4/3 é uma métrica de caminho mais curto em um gráfico planar, e deve ser possível se transformar em uma instância do TSP euclidiano ou TSP no plano com um gap de

ℓ_{1}

$\ell_1$

1 + ϵ

$1+\epsilon$

Luca Trevisan

Ouvi mencionar como uma questão em aberto interessante se os PTASs para problemas em gráficos planares podem ser realizados usando um número constante de níveis de relaxamentos Sherali-Adams ou Lasserre. (Onde a constante depende da razão de aproximação que se deseja obter.) Deveria ser conhecido, ou pelo menos comprovável com as técnicas atuais, que os problemas gráficos que possuem PTASs em gráficos densos (por exemplo, corte máximo) também possuem uma família de polinômios. relaxações de tamanho com lacunas de integralidade arbitrariamente pequenas.

Luca Trevisan

Pergunta relacionada: Existe algum problema provado que qualquer LP de tamanho polinomial não pode fornecer a taxa de aproximação mais conhecida atualmente? É possível provar isso, mesmo para alguns tipos restritos de LPs?

Danu

Respostas:

Como apontado, existem alguns exemplos.

Um exemplo clássico é a correspondência máxima, em que o relaxamento "natural" (sem restrições de conjuntos ímpares) tem uma diferença de 2, enquanto é claro que existe um algoritmo eficiente. Porém, este não se qualifica totalmente, pois existe um LP de tamanho exponencial que pode ser resolvido via elipsóide.

Uma intrigante é a localização das instalações capacitadas. Aqui, o relaxamento natural tem uma lacuna de integralidade ilimitada. No entanto, algoritmos baseados em pesquisa local fornecem aproximações constantes de fatores.

Outro muito interessante (embora seja um problema de maximização) é este artigo: http://www.cis.upenn.edu/~sanjeev/postscript/FOCS09_MaxMin.pdf . Aqui o LP tem uma grande lacuna, e ainda um algoritmo que usa esse LP pode fazer melhor.

Kunal
fonte

Muito obrigado. Esta resposta contém o que eu estava procurando, especialmente o artigo do FOCS escrito por Chakrabarty et al. (este artigo me interessa muito). Portanto, defino esta resposta como aceita. Ainda estou procurando mais exemplos e, portanto, qualquer pessoa que possa dar outros exemplos seria muito apreciada.

Snowie

Existem vários exemplos nos quais um relaxamento de programação semidefinido permite uma aproximação superior às lacunas de integralidade conhecidas para relaxamentos de programação linear.

Por exemplo, o relaxamento de programação linear padrão do corte máximo tem um intervalo de integralidade de 1/2, e isso é verdade mesmo para relaxamentos de programação linear muito mais sofisticados (cf. Vega-Kenyon e Schoenebeck-Trevisan-Tulsiani), mas os Goemans -Williamson SDP algoritmo tem aproximação 0,878 ...

O relaxamento de programação linear de Leighton-Rao do corte mais esparso possui uma lacuna de integralidade , mas o algoritmo SDP de Arora-Rao-Vazirani tem aproximação . $\Omega(\log n)$ $O(\sqrt{\log n})$

Talvez menos conhecido, Karloff e Zwick mostram que o uso do SDP pode aproximar o Max 3SAT, na versão em que as cláusulas podem ter 1, 2 ou 3 literais, dentro de 7/8, enquanto Goemans e Williamson estudaram um relaxamento de programação linear que eles usado para provar uma aproximação de 3/4 (Yannakakis havia dado uma aproximação de 3/4 anteriormente por outros métodos), e o relaxamento de Goemans-Williamson LP do Max 3SAT é facilmente visto como tendo um gap de integralidade 3/4.

Luca Trevisan
fonte

Há também um resultado de Grant na solução de sistemas lineares sobre GF_2. Para sistemas de equações com uma boa solução, você tem um gap de integralidade do SDP (em uma forma muito forte) de 2 enquanto pode usar a Eliminação Gaussiana para resolver exatamente o problema.

YI WU
fonte