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

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 que $2$ . Eu tenho um gráfico de roda, onde cada aresta custa $1$ e a distância entre todos os nós que não estão conectados por arestas é $2$ . O gráfico da roda $W_6$ é 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 seria $7$ tanto para o ideal quanto para o MST.

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

algorithms algorithm-analysis approximation traveling-salesman remo
fonte

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

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

@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:

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 em

v_{0}

$v_0$ ou 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

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 exemplo $v_0,v_4,v_0,v_1,v_0,v_3,v_0,v_6,v_0,v_2,v_0,v_5,v_0$ . Com base nesse tour, a heurística do MST encontra esta solução TSP:

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

$\begin{equation*} \lim_{n\rightarrow\infty} \frac{MST(W_n)}{Opt(W_n)} = \lim_{n\rightarrow\infty}\frac{2n}{n+1} = 2 \end{equation*}$

remo
fonte