Exemplos de instâncias concretas para o algoritmo de Goemans e Williamson

10

Estou interessado nos exemplos explícitos de gráficos para os quais a aplicação do algoritmo de Goemans e Williamson para aproximar o máximo de cortes resulta em 0,878 ... fator de aproximação.

O algoritmo para criar tais instâncias seria perfeito, exemplos e referências explícitos são satisfatórios.

mkatkov
fonte
11
Pergunto-me se você tiver ler este papel eccc.uni-trier.de/report/2005/101
Snowie

Respostas: