Técnicas para provar limites na lacuna de integralidade em LP (SDP)

É necessária uma referência a técnicas para provar que o tamanho de uma lacuna de integralidade é limitado por alguma expressão para um LP específico (ou SDP, mas menos importante). Também seria bom ter uma referência a um local onde são descritas técnicas para minimizar as lacunas de integralidade. Sou novo na área de lacunas de integralidade, que parece bastante grande; portanto, a descrição dos resultados clássicos é mais preferível do que a de algo quente.

ds.algorithms reference-request linear-programming semidefinite-programming integrality-gap Grigory Yaroslavtsev
fonte

Seu título "Lacunas de integralidade no LP (SDP)" é muito geral, é melhor ser mais específico com o título da sua pergunta. O título não é uma tag, deve indicar sua pergunta, algo como: "técnicas para provar limites no gap de integralidade no LP (SDP)".

Kaveh

Respostas:

Para fins de discussão, considere o problema de minimização com a função objetivo . De cabeça para baixo, não consigo pensar em nenhuma técnica dominante para provar lacunas de integralidade. Geralmente, o esboço da prova é a forma implícita na definição de lacuna de integralidade e os detalhes são específicos do problema. $f(x)$

Para mostrar que a diferença de integralidade é pequena (isto é, LP é boa), o seguinte esquema de prova é usual. Use algum tipo de arredondamento (geralmente randomizado) para construir uma solução integral com para cada viável por LP (e para cada instância do problema). Daqui resulta que a diferença de integralidade é no máximo $x'$ $f(x') \le c\cdot f(x)$ $x$ . $c$

Para mostrar que a diferença de integralidade é grande, o seguinte esquema é usual. Exiba uma instância de problema com uma solução viável de LP barata e prove que não há uma boa solução integral.

Warren Schudy
fonte

Parece que deveria ser

, certo?

f (x^{'}) \leq c f (x)

$f(x') \le c f(x)$

Grigory Yaroslavtsev

Obrigado, a abordagem que você descreveu para provar o limite superior do tamanho da lacuna é exatamente o que estou fazendo. Construir

não é um problema no meu caso, e então preciso provar a desigualdade

. Agora isso é feito de uma maneira específica do problema, que dificilmente generaliza para problemas semelhantes da mesma classe, então fiquei curioso se existe algum mecanismo geral para isso.

x^{'}

$x'$

f (x^{'}) \leq c f (x)

$f(x') \le c f(x)$

Grigory Yaroslavtsev

@Grory: Corrigi o bug que você relatou sobre

que deveria ser

x^{'}

$x'$

f (x^{'})

$f(x')$

22810 Warren Schudy

para acrescentar às notas de Warren, existem esquemas de arredondamento cada vez mais sofisticados (e até dependentes), e até esquemas para compactar / cobrir problemas em que o arredondamento pode prejudicar a viabilidade de uma maneira ruim. Dependendo do seu problema, existem referências mais avançadas disponíveis.

Suresh Venkat

Essa é uma maquinaria um pouco pesada para o que você deseja, mas tem havido um grande trabalho em técnicas para projetar LPs (SDPs) cada vez mais refinados que se aproximam cada vez mais do programa inteiro desejado. Uma boa referência que analisa essas abordagens é de Monique Laurent: Uma comparação dos relaxamentos Sherali-Adams, Lovasz-Schrijver e Laserre para a programação 0-1 .

Além disso, não conheço uma única fonte boa de referências: suponho que você pelo menos tenha lido os capítulos relevantes no livro de Vijay Vazirani ?

Suresh Venkat
fonte

Obrigado, sua primeira referência é o que eu tinha em mente e tentei evitar, porque gostaria de ter algo mais simples, se possível.

Grigory Yaroslavtsev

Quanto ao livro de Vijay, ele descreve brevemente a noção de hiato da integralidade e depois vai para a discussão de problemas específicos, sem fornecer técnicas gerais. Suspeito que a noção de gap de integralidade e resultados relevantes sobre ele possa ser muito diferente dos resultados sobre algoritmos de aproximação, porque o primeiro é um problema principalmente geométrico.

Grigory Yaroslavtsev