TSP 1d aproximado com comparações lineares?

O problema unidimensional do caminho do vendedor ambulante é, obviamente, o mesmo que a classificação e, portanto, pode ser resolvido exatamente por comparações no tempo , mas é formulado de tal maneira que a aproximação quanto a exata solução faz sentido. Em um modelo de computação em que as entradas são números reais e é possível arredondar para números inteiros, é fácil aproximar-se de um fator , para qualquer constante , no tempo : encontre min e max, arredonde tudo para um número dentro da distância do valor original e use a classificação radix. Mas os modelos com arredondamento têm uma teoria problemática da complexidade e isso me levou a pensar: e os modelos mais fracos de computação?$O(n\log n)$$1+O(n^{-c})$$c$$O(n)$$(\max-\min)n^{-(c+1)}$

Portanto, com que precisão o TSP unidimensional pode ser aproximado, em um modelo linear de árvore de comparação (cada nó de comparação testa o sinal de uma função linear dos valores de entrada), por um algoritmo cuja complexidade de tempo é $o(n\log n)$ ? O mesmo método de arredondamento permite que qualquer taxa de aproximação da forma $n^{1-o(1)}$ seja alcançada (usando pesquisas binárias para fazer o arredondamento e arredondando muito mais grosseiramente para torná-lo rápido o suficiente). Mas é possível atingir uma taxa de aproximação como $O(n^{1-\epsilon})$ para alguns $\epsilon>0$ ?

EDIT (UPDATE): O limite inferior da minha resposta abaixo foi comprovado (por uma prova diferente) em "Sobre a complexidade de aproximar os passeios euclidianos dos vendedores ambulantes e as árvores mínimas", de Das et al; Algorithmica 19: 447-460 (1997).

---

é possível atingir uma taxa de aproximação como por algum in usando um algoritmo baseado em comparação?ϵ > 0 o ( n log n $O(n^{1-\epsilon})$$\epsilon>0$$o(n\log n)$

Não. Aqui está um limite inferior.

Afirmação. Para qualquer , todo algoritmo de aproximação baseado em comparação requer comparações no pior dos casos.n 1 - ε ohms ( ε n log n $\epsilon>0$$n^{1-\epsilon}$$\Omega(\epsilon n\log n)$

Por "baseado em comparação", quero dizer qualquer algoritmo que apenas consulta a entrada com consultas binárias (Verdadeiro / Falso).

Aqui está uma tentativa de prova. Espero que não haja erros. FWIW, o limite inferior parece provável se estender a algoritmos aleatórios.

---

Corrija qualquer e qualquer arbitrariamente pequeno, mas constante .$n$$\epsilon>0$

Considere apenas oinstâncias de entrada "permutação" que são permutações de . A solução ideal para qualquer uma dessas instâncias custou .$n!$$(x_1,x_2,\ldots,x_n)$$[n]$$n-1$

Defina o custo de uma permutação para ser. Modele o algoritmo como tendo como entrada uma permutação , produzindo uma permutação e pagando o custo .c ( π ) = ∑ i | π ( i + 1 ) - π ( i ) | π π ′ d ( π , π ′ ) = c ( π ′ ∘ π $\pi$$c(\pi) = \sum_i |\pi(i+1) - \pi(i)|$$\pi$$\pi'$$d(\pi,\pi') = c(\pi'\circ \pi)$

Defina como o número mínimo de comparações para qualquer algoritmo baseado em comparação, para obter uma razão competitiva nessas instâncias. Como opt é , o algoritmo deve garantir o custo no máximo .n 1 - ε n - 1 n 2 - $C$$n^{1-\epsilon}$$n-1$$n^{2-\epsilon}$

Mostraremos .$C\ge \Omega(\epsilon n\log n)$

Defina como, para qualquer saída possível , a fração de entradas possíveis para a qual a saída alcançaria um custo no máximo . Essa fração é independente de .π ′ π ′ n 2 - ϵ π $P$$\pi'$$\pi'$$n^{2-\epsilon}$$\pi'$

π c ( π ) n 2 - ε π ' I P d ( π , I ) n 2 - ε d ( π , I ) = C ( π $P$ também é igual à probabilidade de que, para uma permutação aleatória , seu custo seja no máximo . (Para ver por que, considere como permutação de identidade Então é a fração de entradas para a qual no máximo , mas .)$\pi$$c(\pi)$$n^{2-\epsilon}$$\pi'$$I$$P$$d(\pi,I)$$n^{2-\epsilon}$$d(\pi,I) = c(\pi)$

Lema 1. .$C \ge \log_2 1/P$

Prova. Corrija qualquer algoritmo que sempre use comparações inferiores aA árvore de decisão do algoritmo possui profundidade menor que , portanto, existem menos de folhas e, para alguma permutação de saída , o algoritmo fornece como saída para mais de um fração das entradas. Por definição de , para pelo menos uma dessas entradas, a saída custa mais que . QEDlog 2 1 / P 1 / P π ′ π ′ P P π ′ n 2 - $\log_2 1/P$$\log_2 1/P$$1/P$$\pi'$$\pi'$$P$$P$$\pi'$$n^{2-\epsilon}$

Lema 2. .$P \le \exp(-\Omega(\epsilon n\log n))$

Antes de apresentarmos a prova do Lema 2, observe que os dois lemas juntos apresentam a afirmação:

$$C ~\ge~ \log_2 \frac{1}{P} ~=~ \log_2 \exp(\Omega(\epsilon n\log n)) ~=~ \Omega(\epsilon n\log n).$$

---

Prova de lema 2. Seja uma permutação aleatória. Lembre-se de que é igual à probabilidade de seu custo ser no máximo . Digamos que qualquer par seja uma aresta com custo, então é a soma dos custos de borda.P c ( π ) n 2 - ϵ ( i , i + 1 ) | π ( i + 1 ) - π ( i ) | c ( π $\pi$$P$$c(\pi)$$n^{2-\epsilon}$$(i,i+1)$$|\pi(i+1)-\pi(i)|$$c(\pi)$

Suponha que .$c(\pi) \le n^{2-\epsilon}$

Então, para qualquer , no máximo das arestas custam ou mais. Digamos que bordas de custo menores que sejam baratas .n 2 - ϵ / q q $q>0$$n^{2-\epsilon}/q$$q$$q$

Corrija . Substituindo e simplificando, no máximo das arestas não são baratas. n 1 - ϵ /$q=n^{1-\epsilon/2}$$n^{1-\epsilon/2}$

Assim, pelo menos das arestas são baratas. Assim, existe um conjunto contendo arestas baratas.S n /$n - n^{1-\epsilon/2} \ge n/2$$S$$n/2$

Afirmação. Para qualquer conjunto de arestas, a probabilidade de que todas as arestas em sejam baratas é no máximo .N / 2 S exp ( - Ω ( ε N log N ) $S$$n/2$$S$$\exp(-\Omega(\epsilon n \log n))$

Antes de provarmos a afirmação, observe que ela implica o lema da seguinte forma. Pela alegação e pelo limite da união ingênua, a probabilidade de que exista esse conjunto é no máximo ($S$≤exp(S(n)-Ω(εNlogN))≤exp(-Ω(εNlogN))

$${n\choose n/2} \exp(-\Omega(\epsilon n \log n)) ~\le~ 2^n \exp(-\Omega(\epsilon n \log n))$$ $$~\le~ \exp(O(n) -\Omega(\epsilon n \log n)) ~\le~ \exp(-\Omega(\epsilon n \log n)).$$

---

Prova de reivindicação. Escolha pelo seguinte processo. Escolha uniformemente entre , escolha uniformemente entre e escolha uniformemente entre etc.π ( 1 ) [ n ] π ( 2 ) [ n ] - { π ( 1 ) } π ( 3 ) [ n ] - { π ( 1 ) , π ( 2 ) $\pi$$\pi(1)$$[n]$$\pi(2)$$[n] - \{\pi(1)\}$$\pi(3)$$[n]-\{\pi(1),\pi(2)\}$

Considere qualquer borda em . Considere o tempo logo após a escolha de , quando está prestes a ser escolhido. Independentemente das primeiras escolhas (para para ), há pelo menos opções para e no máximo daquelas as opções darão ao limite custo menor que (tornando-o barato).S π ( i ) π ( i + 1 ) i π ( j ) j ≤ i n - i π ( i + 1 ) 2 n 1 - ϵ / 2 ( i , i + 1 ) n 1 - ϵ /$(i,i+1)$$S$$\pi(i)$$\pi(i+1)$$i$$\pi(j)$$j\le i$$n-i$$\pi(i+1)$$2n^{1-\epsilon/2}$$(i,i+1)$$n^{1-\epsilon/2}$

Assim, condicionado nas primeiras escolhas, a probabilidade de que a borda é barato, é, no máximo, . Portanto, a probabilidade de que todas as arestas em sejam baratas é no máximo Como , há pelo menos arestas em com . Portanto, este produto é no máximo 2 n 1 - ϵ /$i$ n/2S∏(i,i+1)∈S2n 1 - ϵ /$\frac{2n^{1-\epsilon/2}}{n-i}$$n/2$$S$| S| ≥n/2n/4Sn-i≥n/4(2n 1 - ϵ /

$$\prod_{(i,i+1)\in S} \frac{2n^{1-\epsilon/2}}{n-i}.$$ $|S|\ge n/2$$n/4$$S$$n-i\ge n/4$ $$\big(\frac{2n^{1-\epsilon/2}}{n/4}\big)^{n/4} ~\le~(8n^{-\epsilon/2})^{n/4} ~=~\exp(O(n)-\Omega(\epsilon n \log n)) ~=~\exp(-\Omega(\epsilon n \log n)).$$

QED