Por que este gráfico mostra a rigidez do limite de 2 aproximações da heurística do MST?

7

Esse é um problema de lição de casa que me foi dado e tenho vasculhado meu cérebro há horas (por isso estou satisfeito com algumas dicas). Eu já sei que a taxa de aproximação não pode ser pior do que2. Eu tenho um gráfico de roda, onde cada aresta custa1 1 e a distância entre todos os nós que não estão conectados por arestas é 2. O gráfico da rodaW6 é este:

Marquei em azul o que acredito ser a saída de um algoritmo heurístico do MST. Mas também acho que essa é a solução ideal, pois todos os nós podem ser visitados apenas uma vez. Portanto, o custo do passeio seria7 tanto para o ideal quanto para o MST.

Não vejo como esse tipo de gráfico mostra que o 2O limite de aproximação da heurística do MST é rígido (não necessariamente nesta instância, mas os gráficos Wnem geral). Alguém pode me esclarecer?

remo
fonte
11
Nenhum exemplo único pode "provar que a aproximação do MST ao TSP é uma aproximação de 2", pois ser uma aproximação de 2 exige estar dentro de um fator de dois dos ótimos em todos os gráficos. O que esse gráfico deve fazer é provar que o MST não é melhor que uma aproximação 2, mostrando um gráfico no qual ele sai exatamente por um fator de dois. A propósito, presumivelmente deve haver uma borda preta de V1 a V6.
David Richerby
@DavidRicherby Eu sei por que não é pior que uma aproximação 2, essa deveria ser a pior das hipóteses, mostrando que o limite é apertado. Ou talvez uma série de n crescentes faça com que a razão converja para dois. E, tanto quanto eu entendo, as únicas bordas pretas devem ser os raios. Embora ter nós no círculo conectados ao custo 1 não mude o passeio, eu acho.
oarfish
11
Sugiro que você reformule sua pergunta para deixar isso claro.
David Richerby
Não vejo como esse tipo de gráfico mostra que o limite de 2 aproximações da heurística do MST é rígido parece esclarecer minha intenção. Como você sugeriria editar a pergunta?
oarfish
2
@oarfish O título é o maior problema; faz as pessoas esperarem um certo tipo de pergunta. Então eles lêem coisas que não se encaixam, pulam o resto e comentam.
Raphael

Respostas:

4

Há muita liberdade no algoritmo: várias árvores abrangentes mínimas e vários passeios eulerianos correspondentes. Tente encontrar a pior escolha e mostre que ela produz um passeio inferior. O que você está mostrando é que o algoritmo poderia fazer esta escolha, e assim poderia produzir uma aproximação inferior.

Se você não gosta dessa idéia de escolha, às vezes pode garantir que o algoritmo faça as escolhas desejadas, ajustando levemente os pesos.

Yuval Filmus
fonte
Onde a correspondência mínima entra em jogo? Não estou falando do Christofides, apenas da heurística do MST. E, tanto quanto eu posso ver e experimentar no papel, não importa se eu começo com o MST que é uma estrela centrada emv0 0ou um que compreende o ciclo externo menos uma aresta mais um dos raios. Talvez eu tenha um mal-entendido fundamental, mas acho que é bastante simples.
oarfish
@ararfish Certo, o algoritmo de Christofides é realmente melhor.
Yuval Filmus
Eu não percebi isso antes, mas esta é realmente a direção certa. Basta selecionar o pior passeio possível. Não vi muitos deles que não são equivalentes quando se trata do tour TSP gerado.
oarfish
3

O gráfico que publiquei está faltando algumas arestas, os nós adjacentes no ciclo devem estar conectados. ( Editar : Corrigido o gráfico com o tour TSP).

O gráfico real é este

Minha solução é a seguinte. Agora, o MST calculado para a heurística do MST é obviamente

permitindo muitos passeios euler, entre outros:

onde os nós do ciclo podem ser visitados em qualquer ordem. Agora, qualquer um dos passeios é válido para que possamos escolher o pior, por exemplov0 0,v4,v0 0,v1 1,v0 0,v3,v0 0,v6,v0 0,v2,v0 0,v5,v0 0. Com base nesse tour, a heurística do MST encontra esta solução TSP:

Agora, já que todas as arestas custam 1 1 ee todos os nós não conectados no gráfico têm distância 2, o custo do passeio é 2(n-1 1)+2 onde o passeio ideal teria custado n+1 1. No limite

limnMST(Wn)Opt(Wn)=limn2nn+1 1=2

remo
fonte