A importância do hiato da integralidade

Eu sempre tive problemas para entender a importância do gap de integralidade (IG) e os limites dele. IG é a razão de (a qualidade de) uma resposta inteira ideal para (a qualidade de) uma solução real ótima do relaxamento do problema. Vamos considerar a cobertura de vértices (VC) como um exemplo. O VC pode ser declarado como encontrando uma solução inteira ideal do seguinte conjunto de equações lineares:

Nós ter zero / um variáveis avaliadas S para cada vértice do gráfico . As equações são: para e para cada aresta . Estamos procurando valores que minimizem . v ∈ V ( G ) G 0 ≤ x v ≤ 1 v ∈ V ( G ) 1 ≤ x v + x u u v ∈ E ( G ) ∑ v ∈ V ( G ) x $x_v$$v \in V(G)$$G$$0 \leq x_v \leq 1$$v\in V(G)$$1 \leq x_v+x_u$$uv \in E(G)$$\sum_{v \in V(G)} x_v$

O relaxamento desse problema permite valores reais entre e portanto o espaço das soluções é maior e uma solução real ideal pode ser menor do que uma solução inteira ideal que queremos encontrar. Portanto, precisamos executar um processo de "arredondamento" na resposta real ótima obtida da programação linear para encontrar uma solução inteira. A solução inteira ideal estará entre a solução real ideal e o resultado do processo de arredondamento. IG é a razão de uma solução inteira ideal para uma solução real ideal e não diz nada sobre o processo de arredondamento. O processo de arredondamento pode (em teoria) ignorar completamente a solução real e calcular diretamente a solução inteira ideal.$0$$1$

Por que as pessoas estão interessadas em provar limites no IG?

As lacunas de integralidade representam essencialmente os limites inerentes a um relaxamento linear ou convexo específico na aproximação de um programa inteiro. Geralmente, se a diferença de integralidade de um relaxamento específico é , qualquer algoritmo de aproximação baseado nesse relaxamento não pode esperar fazer melhor do que uma aproximação . Portanto, no mínimo, as lacunas de integralidade são de interesse dos projetistas de algoritmos, pois sugerem limitações em certas técnicas. $x$$x$

Então, por que não criar outro relaxamento de LP ou mudar para outras técnicas e seguir em frente? A programação linear e convexa provou ser central para os algoritmos de aproximação; para muitos problemas, a lacuna de integralidade de uma formulação natural de LP ou SDP é igual à taxa de aproximação do melhor algoritmo, bem como à dureza da taxa de aproximação. Esta é apenas uma observação empírica, mas significa que provar uma lacuna de integralidade pode sugerir consequências muito mais fortes de um algoritmo aprimorado ou limite inferior.

Pode haver razões mais profundas e mais rigorosas para esse fenômeno. Por exemplo, assumindo a conjectura de jogos únicos, sabe-se que a taxa de aproximação e a taxa de inadequação para problemas de satisfação de restrição é igual à diferença de integralidade de um relaxamento simples do SDP (consulte Algoritmos ótimos e resultados de inadequação para cada CSP? Por Prasad Raghavendra)

Finalmente, as lacunas de integralidade representam limites inferiores incondicionais . Normalmente, precisamos confiar em suposições não comprovadas (por exemplo, ) se quisermos progredir em limites inferiores, mas para modelos restritos de computação, às vezes podemos fugir sem isso (ver notas da aula de Luca Trevisan). As lacunas de integralidade, sendo puramente geométricas e não computacionais, são uma maneira de obter limites inferiores bastante poderosos sem a bagagem de suposições extras.$P \neq NP$

Suponha que o seu problema de interesse é um problema de minimização e que você desenvolveu um algoritmo -approximate. Se, em uma determinada entrada, seu algoritmo gerar uma solução de custo , o cálculo do algoritmo mais sua análise fornecerão um certificado de que, nessa entrada, o ideal é pelo menos . Claramente, é pelo menos o ideal, portanto, para cada entrada, podemos certificar um limite inferior ao ideal, que é pelo menos uma fração de do próprio ideal.c a / c a 1 /$a$$c$$a/c$$a$$1/c$

Em todos os algoritmos baseados em relaxações convexas (LP e SDP) que eu conheço, o limite inferior certificado ao ótimo é dado pelo ideal do relaxamento. Se o relaxamento tiver uma lacuna de integralidade , não será possível obter uma taxa de aproximação melhor que , a menos que na análise se introduza uma técnica de limite inferior para o ideal que é mais forte que o limite inferior fornecido pelo relaxamento.$I$$I$

A diferença de integralidade é um indicador útil de quão bem um IP pode ser aproximado. Talvez seja melhor pensar nisso de uma maneira informal e intuitiva. Uma lacuna de alta integralidade implica que certos métodos não funcionam. Certos métodos primários / duplos, por exemplo, dependem de uma pequena lacuna de integralidade. Para o LP padrão Verl Cover, o LP duplo pede uma correspondência máxima. Nesse caso, podemos fazer o seguinte:

• encontre uma solução fracionária ideal para o LP duplo (uma correspondência fracionária máxima)$\boldsymbol{y}$
• multiplique a solução por um fator de 2 (dobre todos os pesos das arestas)$\boldsymbol{y}$
• converta isso em uma integral viável para o LP primitivo (cada aresta dá metade do seu peso do vetor a cada um dos pontos finais no vetor , então cada é substituído por ).$\boldsymbol{x}$$2\boldsymbol{y}$$\boldsymbol{x}$$x_i$$\min(\lfloor x_i\rfloor, 1)$

Nesse caso, essa estratégia simples funciona e acabamos com uma solução integral viável para o LP primário, cujo peso não é mais do que o dobro do peso de uma solução viável para o LP duplo. Como o peso de uma solução viável para o LP duplo é um limite inferior para o OPT, esse é um algoritmo de 2 aproximações.

Agora, de onde vem a lacuna de integralidade? O IG é 2 neste caso, mas isso por si só não implica que o algoritmo funcione. Em vez disso, sugere que pode funcionar. E se o IG fosse superior a 2, garantiria que a estratégia simples nem sempre funcionasse. No mínimo, teríamos que multiplicar a solução dupla pelo IG. Portanto, a diferença de integralidade às vezes nos diz o que não funciona. A lacuna de integralidade também pode indicar que tipo de fator de aproximação podemos esperar. Uma pequena lacuna de integralidade sugere que investigar estratégias de arredondamento, etc., pode ser uma abordagem que vale a pena.

Para um exemplo mais interessante, considere o problema do Conjunto de e a poderosa técnica de aproximação do problema usando -nets (Brönnimann & Goodrich, 1995) . Muitos problemas podem ser formulados como instâncias do Hitting Set, e uma estratégia que tem sido bem-sucedida em muitos problemas é fazer isso, basta encontrar um bom localizador de rede, ou seja, um algoritmo para construir pequenas e pôr em marcha tudo através o meta-algoritmo B&G. Assim, as pessoas (inclusive eu) tentam encontrar localizadores de rede para instâncias restritas do Hitting Set que, para qualquer , podem criar uma do tamanho , onde a função$\varepsilon$$\varepsilon$$\varepsilon$$\varepsilon$$f(1/\varepsilon)$$f$deve ser o menor possível. Ter é uma meta típica; isso daria uma aproximação .$f(1/\varepsilon) = \mathcal{O}(1/\varepsilon)$$\mathcal{O}(1)$

Como se vê, a melhor função possível é limitada pela lacuna de integralidade de um determinado LP para Hitting Set (Even, Rawitz, Shahar, 2005) . Especificamente, as soluções integrais e fracionárias ideais satisfazem . Para instâncias irrestritas do Hitting Set, o intervalo de integralidade é , mas ao formular outro problema como Hitting Set, o IG pode ser menor. Em este exemplo os autores mostram como encontrar -nets de tamanho$f$$\mathrm{OPT}_I \leq f(\mathrm{OPT}_f)$$\Theta(\log(m))$$\varepsilon$$\mathcal{O}((1/\varepsilon) \log \log (1/\varepsilon))$para as instâncias restritas do Conjunto de Acertos que correspondem ao problema de acertar caixas paralelas ao eixo. Dessa maneira, eles melhoram o fator de aproximação mais conhecido para esse problema. É um problema em aberto se isso pode ser melhorado ou não. Se, para essas instâncias restritas do Hitting Set, o IG do Hitting Set LP for , seria impossível projetar o net finder garantindo -nets do tamanho , pois isso implicaria a existência de um algoritmo que garante conjuntos de acertos integrais de tamanho , mas desde$\Theta(\log \log m)$$\varepsilon$$o((1/\varepsilon) \log \log (1/\varepsilon))$$o(\mathrm{OPT}_f \log\log \mathrm{OPT}_f)$$\mathrm{OPT}_f\leq m$isso implicaria uma menor lacuna de integralidade. Portanto, se a diferença de integralidade for grande, provar que isso poderia impedir as pessoas de perder tempo procurando bons buscadores de rede.

Quando você está criando um algoritmo de aproximação para algum problema de maximização difícil de NP, existem vários valores com os quais você pode se interessar: OPT, o valor ideal do seu problema, que é o mesmo que OPT (IP), o ideal valor de qualquer formulação correta de IP do seu problema. Há também OPT (LP), o valor ideal do relaxamento linear do seu IP.

$OPT(LP) \geq OPT(IP)$

Finalmente, há V, o valor da solução que você obtém arredondando a solução LP. Você gostaria de provar que para mostrar que seu algoritmo é uma aproximação , mas geralmente não é possível fazer isso diretamente, já que você não possui um mantenha o espaço da solução. Em vez disso, o que quase sempre é comprovado é o . É claro que isso implica em , mas é mais forte. Em particular, se a diferença de integralidade da sua formulação de IP for maior que , a instrução acima será falsa em geral, uma vez que seu procedimento de arredondamento termina com uma solução integral.$V > \frac{OPT(IP)}{c}$$c$$V \geq \frac{OPT(LP)}{c}$$V > \frac{OPT(IP)}{c}$$c$

Portanto, o cerne é o seguinte: o LP fornece uma solução que você sabe que é "boa" e você deseja arredondá-la para algo que é "quase tão bom". Se a diferença de integralidade for grande, isso é impossível em geral, pois nunca haverá um procedimento que garanta uma solução integral "quase tão boa" quanto uma solução de LP - porque, às vezes, elas não existem!

Você está certo no fato de que a lacuna de integralidade de um relaxamento não tem nada a ver com qualquer algoritmo de arredondamento. Essas são duas noções diferentes. Uma lacuna de integralidade é uma propriedade de um relaxamento específico. Ou seja, quanto maior é o valor desse relaxamento em comparação com o valor integral ideal?

Por que nos preocupamos com relaxações lineares / convexas? Aproximar eficientemente um valor integral. Por isso, normalmente falamos sobre relaxamentos apenas nos casos em que o valor ideal é difícil de calcular e estamos interessados ​​em aproximações eficientes. As lacunas de integralidade nos mostram as limitações inerentes ao que pode ser alcançado por essas técnicas.

Então, por que nos preocupamos com algoritmos de arredondamento além do relaxamento? Usamos algoritmos de arredondamento para resolver o problema algorítmico de encontrar uma solução quase ideal, em vez de apenas aproximar o valor de uma solução ótima. Além disso, algoritmos de arredondamento geralmente são usados ​​para limitar a lacuna de integralidade de um relaxamento em primeiro lugar.

Tecnicamente, a diferença de integralidade é para uma formulação IP específica, não (como você a formulou) a relação entre o melhor relaxamento linear e a solução ideal (que parece quantificar sobre TODAS as formulações IP).

Uma lacuna de integralidade é importante porque mostra os limites da formulação de LP específica que está sendo usada. Se eu sei que um relaxamento específico tem uma lacuna de integralidade de , também sei que, se algum dia eu provar que é um limite melhor que , precisarei usar uma formulação diferente.$c$$c$

Havia um artigo muito interessante "Sobre a vantagem da codificação de rede para melhorar o rendimento da rede", que mostrou que a lacuna de integralidade do "relaxamento de corte bidirecionado" para o problema da árvore Steiner é exatamente igual a um tipo de "vantagem de codificação" na comunicação em rede. Não conheço muitos outros artigos semelhantes. No entanto, deve-se notar também que são conhecidos relaxamentos aparentemente melhores de LP para o problema da árvore de Steiner (por exemplo, veja o novo algoritmo de aproximação baseado em LP hipergráfico de Byrka et al em STOC 2010, eu também sou vergonhosamente voluntário por co-autor de alguns trabalhos recentes que estudavam o hipergráfico LP).

A maioria das respostas já abordou o principal motivo para se preocupar com a lacuna de integralidade, a saber, que um algoritmo de aproximação baseado apenas no uso do limite fornecido pelo relaxamento não pode esperar provar uma razão melhor que a lacuna de integralidade. Deixe-me dar duas outras razões meta pelas quais a diferença de integralidade é um guia útil. Para uma grande classe de problemas de otimização combinatória, a equivalência de separação e otimização mostra que algoritmos exatos estão intimamente relacionados ao casco convexo das soluções viáveis ​​para o problema. Assim, a perspectiva geométrica e algorítmica estão intimamente ligadas. Uma equivalência formal semelhante não é conhecida para algoritmos de aproximação, mas é um guia útil - algoritmos andam de mãos dadas com relaxações geométricas. A inovação algorítmica acontece quando as pessoas têm um objetivo concreto a melhorar.