TSP 1d approximatif avec comparaisons linéaires?

$O(n\log n)$$1+O(n^{-c})$$c$$O(n)$$(\max-\min)n^{-(c+1)}$de sa valeur d'origine, puis utilisez le tri radix. Mais les modèles avec arrondi ont une théorie de complexité problématique et cela m'a amené à me demander, qu'en est-il des modèles de calcul plus faibles?

Ainsi, avec quelle précision le TSP unidimensionnel peut-il être approximé, dans un modèle d'arbre de comparaison linéaire de calcul (chaque nœud de comparaison teste le signe d'une fonction linéaire des valeurs d'entrée), par un algorithme dont la complexité temporelle est ? La même méthode d'arrondi permet d'obtenir n'importe quel rapport d'approximation de la forme n ^ {1-o (1)} (en utilisant des recherches binaires pour effectuer l'arrondi, et en arrondissant beaucoup plus grossièrement pour le rendre assez rapide). Mais est-il possible d'atteindre même un rapport d'approximation comme O (n ^ {1- \ epsilon}) pour certains \ epsilon> 0 ?n 1 - o ( 1 ) O ( n 1 - ϵ ) ϵ > $o(n\log n)$$n^{1-o(1)}$$O(n^{1-\epsilon})$$\epsilon>0$

EDIT (UPDATE): La limite inférieure dans ma réponse ci-dessous a été prouvée (par une preuve différente) dans "Sur la complexité de l'approximation des tournées des vendeurs itinérants euclidiens et des arbres couvrant minimum", par Das et al; Algorithmica 19: 447-460 (1997).

---

est-il possible d'atteindre même un rapport d'approximation comme pendant un certain temps en utilisant un algorithme basé sur la comparaison?$O(n^{1-\epsilon})$o ( n log n $\epsilon>0$$o(n\log n)$

Non, voici une borne inférieure.

Prétendre. Pour tout , chaque algorithme d'approximation basé sur la comparaison nécessite des comparaisons dans le pire des cas.n 1 - ϵ Ω ( ϵ n log n $\epsilon>0$$n^{1-\epsilon}$$\Omega(\epsilon n\log n)$

Par "basé sur la comparaison", j'entends tout algorithme qui interroge uniquement l'entrée avec des requêtes binaires (Vrai / Faux).

Voici une tentative de preuve. Espérons qu'il n'y ait pas d'erreurs. FWIW la borne inférieure semble susceptible de s'étendre aux algorithmes randomisés.

---

Fixez tout et tout arbitrairement petit mais constant .ϵ > $n$$\epsilon>0$

Considérez juste leinstances d'entrée de "permutation" qui sont des permutations de . La solution optimale pour une telle instance a coûté .( x 1 , x 2 , … , x n ) [ n ] n - $n!$$(x_1,x_2,\ldots,x_n)$$[n]$$n-1$

Définissez le coût d'une permutation comme étant. Modélisez l'algorithme en prenant comme entrée une permutation , en sortant une permutation et en payant le coût .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)$

Définissez comme étant le nombre minimum de comparaisons pour tout algorithme basé sur la comparaison pour atteindre le rapport compétitif sur ces instances. Puisque opt est , l'algorithme doit garantir le coût au plus .n 1 - ϵ n - 1 n 2 - $C$$n^{1-\epsilon}$$n-1$$n^{2-\epsilon}$

Nous allons montrer .$C\ge \Omega(\epsilon n\log n)$

Définissez comme étant, pour toute sortie , la fraction des entrées possibles pour lesquelles la sortie coûterait au plus . Cette fraction est indépendante de .π ′ π ′ n 2 - ϵ π $P$$\pi'$$\pi'$$n^{2-\epsilon}$$\pi'$

π c ( π ) n 2 - ϵ π ′ I P d ( π , I ) n 2 - ϵ d ( π , I ) = c ( π $P$ également égal à la probabilité que, pour une permutation aléatoire , son coût soit au plus . (Pour voir pourquoi, prenons comme permutation d'identité Alors est la fraction des entrées pour lesquelles au plus , mais .)$\pi$$c(\pi)$$n^{2-\epsilon}$$\pi'$$I$$P$$d(\pi,I)$$n^{2-\epsilon}$$d(\pi,I) = c(\pi)$

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

Preuve. Corrigez tout algorithme qui utilise toujours moins de comparaisons queL'arbre de décision de l'algorithme a une profondeur inférieure à , il y a donc moins de feuilles, et, pour certaines permutations de sortie , l'algorithme donne comme sortie pour plus d'un fraction des entrées. Par définition de , pour au moins une de ces entrées, la sortie donne un coût supérieur à . 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}$

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

Avant de donner la preuve du lemme 2, notons que les deux lemmes donnent ensemble la revendication:

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

---

Preuve du lemme 2. Soit une permutation aléatoire. Rappelons que est égal à la probabilité que son coût soit au maximum . Disons que toute paire est une arête avec un coût, donc est la somme des coûts de bord.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)$

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

Ensuite, pour tout , au plus des arêtes ont coûté ou plus. Disons que les arêtes de coût inférieur à sont bon marché .n 2 - ϵ / q q $q>0$$n^{2-\epsilon}/q$$q$$q$

Fixez . Substituer et simplifier, au plus des bords ne sont pas bon marché. n 1 - ϵ /$q=n^{1-\epsilon/2}$$n^{1-\epsilon/2}$

Ainsi, au moins des arêtes sont bon marché. Ainsi, il existe un ensemble contenant bords bon marché.S n /$n - n^{1-\epsilon/2} \ge n/2$$S$$n/2$

Prétendre. Pour tout ensemble donné de arêtes, la probabilité que toutes les arêtes de soient bon marché est au plus .n / 2 S exp ( - Ω ( ϵ n log n ) $S$$n/2$$S$$\exp(-\Omega(\epsilon n \log n))$

Avant de prouver l'allégation, notez qu'elle implique le lemme comme suit. D'après la revendication et la liaison naïve, la probabilité qu'il existe un tel ensemble est au plus ($S$

$${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)).$$

---

Preuve de réclamation. Choisissez par le processus suivant. Choisissez uniformément dans , puis choisissez uniformément dans , puis choisissez uniformément dans , etc.π ( 1 ) [ n ] π ( 2 ) [ n ] - { π ( 1 ) $\pi$$\pi(1)$$[n]$$\pi(2)$$[n] - \{\pi(1)\}$[ n ] - { π ( 1 ) $\pi(3)$$[n]-\{\pi(1),\pi(2)\}$

Considérons une arête à . Considérez le temps juste après que a été choisi, quand est sur le point d'être choisi. Quels que soient les premiers choix (pour pour ), il y a au moins choix pour , et au plus de ceux-ci les choix donneront le bord moins cher que (ce qui le rend bon marché).S π ( i ) π ( i + 1 ) i π ( j ) j ≤ i n - i π ( i + 1 ) 2 n 1 - $(i,i+1)$$S$$\pi(i)$$\pi(i+1)$$i$$\pi(j)$$j\le i$$n-i$$\pi(i+1)$ (i,i+1)n 1 $2n^{1-\epsilon/2}$$(i,i+1)$$n^{1-\epsilon/2}$

Ainsi, conditionnée aux premiers choix, la probabilité que l'arête soit bon marché est au maximum . Ainsi, la probabilité que toutes les arêtes de soient bon marché est au plus Puisque , il y a au moins arêtes dans avec . Ainsi, ce produit est au maximum 2 n $i$ n/2S∏(i,i+1)∈S2n 1 - ϵ /$\frac{2n^{1-\epsilon/2}}{n-i}$$n/2$$S$| S| ≥n/

$$\prod_{(i,i+1)\in S} \frac{2n^{1-\epsilon/2}}{n-i}.$$ $|S|\ge n/2$S n - i ≥ n / 4 ( 2 n 1 - ϵ /$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