Приблизительный 1d TSP с линейными сравнениями?

$O(n\log n)$$1+O(n^{-c})$$c$$O(n)$$(\max-\min)n^{-(c+1)}$его первоначального значения, а затем используйте основную сортировку. Но модели с округлением имеют проблематичную теорию сложности, и это заставило меня задуматься, а как насчет более слабых моделей вычислений?

Итак, насколько точно может быть аппроксимирован одномерный TSP в модели вычисления с линейным деревом сравнения (каждый узел сравнения проверяет знак линейной функции входных значений) алгоритмом, сложность которого по времени равна ? Тот же метод округления позволяет достичь любого отношения аппроксимации в форме (с помощью бинарного поиска для округления и округления гораздо более грубого, чтобы сделать его достаточно быстрым). Но возможно ли достичь даже отношения аппроксимации, такого как для некоторого ?$o(n\log n)$$n^{1-o(1)}$$O(n^{1-\epsilon})$$\epsilon>0$

РЕДАКТИРОВАТЬ (ОБНОВЛЕНИЕ): Нижняя граница в моем ответе ниже была доказана (другим доказательством) в «О сложности приближения евклидовых туров коммивояжера и минимального охвата деревьев», Das et al; Algorithmica 19: 447-460 (1997).

---

Можно ли достичь даже отношения аппроксимации, например, для некоторого за времени, используя алгоритм сравнения?$O(n^{1-\epsilon})$$\epsilon>0$$o(n\log n)$

Нет. Вот нижняя граница.

Запрос. Для любого каждого алгоритма аппроксимации на основе сравнения требуется сравнение в худшем случае.$\epsilon>0$$n^{1-\epsilon}$$\Omega(\epsilon n\log n)$

Под «сравнением» я подразумеваю любой алгоритм, который запрашивает входные данные только с помощью двоичных (True / False) запросов.

Вот попытка доказательства. Надеюсь, ошибок нет. Впрочем, нижняя граница, вероятно, распространяется на рандомизированные алгоритмы.

---

Зафиксируйте любое и любое сколь угодно маленькое, но постоянное .ϵ > $n$$\epsilon>0$

Рассмотрим тольковходные экземпляры "перестановки" которые являются перестановками . Оптимальное решение для любого такого случая имеет стоимость .( x 1 , x 2 , … , x n ) [ n ] n - $n!$$(x_1,x_2,\ldots,x_n)$$[n]$$n-1$

Определите стоимость перестановки как, Смоделируйте алгоритм так, чтобы он принимал в качестве входных данных перестановку , выводил перестановку и оплачивал стоимость .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)$

Определите как минимальное количество сравнений для любого алгоритма, основанного на сравнении, для достижения конкурентного отношения в этих случаях. Поскольку opt равен , алгоритм должен гарантировать стоимость не более .n 1 - ϵ n - 1 n 2 - $C$$n^{1-\epsilon}$$n-1$$n^{2-\epsilon}$

Мы покажем .$C\ge \Omega(\epsilon n\log n)$

Определите чтобы для любого возможного вывода доля возможных входов, для которых выход достиг бы стоимости, не превышала . Эта фракция не зависит от .π ′ π ′ n 2 - ϵ π $P$$\pi'$$\pi'$$n^{2-\epsilon}$$\pi'$

π $P$ также равняется вероятности того, что для случайной перестановки ее стоимость не превосходит . (Чтобы понять почему, в качестве тождественной перестановки примем . Тогда - это доля входных данных, для которых не более , но .)$\pi$п 2 - & epsi ; л ' Я Р д ( л , я ) п 2 - & epsi ; г ( л , я ) = C ( л $c(\pi)$$n^{2-\epsilon}$$\pi'$$I$$P$$d(\pi,I)$$n^{2-\epsilon}$$d(\pi,I) = c(\pi)$

Лемма 1. .$C \ge \log_2 1/P$

Доказательство. Исправьте любой алгоритм, который всегда использует меньше чем сравнений. Дерево решений для алгоритма имеет глубину меньше , поэтому число листов меньше , и для некоторой выходной перестановки алгоритм выдает качестве выходных данных для более чем доля входов. По определению , по крайней мере для одного такого входа, вывод дает стоимость, превышающую . 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}$

Лемма 2. .$P \le \exp(-\Omega(\epsilon n\log n))$

Прежде чем дать доказательство леммы 2, обратите внимание, что две леммы вместе дают утверждение:

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

---

Доказательство леммы 2. Пусть - случайная перестановка. Напомним, что равно вероятности того, что его стоимость не превосходит . Скажем, что любая пара является ребром со стоимостью, поэтому - сумма затрат на ребро.P c ( π ) n 2 - ϵ ( i , i + 1 ) | π ( i + 1 ) - π ( i ) | с ( π $\pi$$P$$c(\pi)$$n^{2-\epsilon}$$(i,i+1)$$|\pi(i+1)-\pi(i)|$$c(\pi)$

Предположим, что .$c(\pi) \le n^{2-\epsilon}$

Тогда для любого не более ребер будут стоить или больше. Скажите , что края стоимости меньше , чем являются дешево .n 2 - ϵ / q q $q>0$$n^{2-\epsilon}/q$$q$$q$

Исправьте . Подстановка и упрощение не более ребер недешевы. n 1 - ϵ /$q=n^{1-\epsilon/2}$$n^{1-\epsilon/2}$

Таким образом, по крайней мере ребер дешевы. Таким образом, существует множество содержащее дешевых ребер.S n /$n - n^{1-\epsilon/2} \ge n/2$$S$$n/2$

Запрос. Для любого заданного множества из ребер вероятность того, что все ребра в дешевые, не .п / 2 S ехр ( - Ω ( ε п войти п ) $S$$n/2$$S$$\exp(-\Omega(\epsilon n \log n))$

Прежде чем доказать утверждение, отметим, что оно подразумевает следующую лемму. По претензии и наивным союза , связанного, вероятность того, что какие -то там существует такое множество самое большее ($S$≤ ехр ( О ( п ) - Ω ( ε п войти п ) ) ≤ ехр ( - Q , ( ε п лог п ) )

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

---

Доказательство претензии. Выберите следующим процессом. Выберите равномерно из , затем выберите равномерно из , затем выберите равномерно из и т. д.π ( 1 ) [ n $\pi$$\pi(1)$$[n]$$\pi(2)$$[n] - \{\pi(1)\}$$\pi(3)$$[n]-\{\pi(1),\pi(2)\}$

Рассмотрим любое ребро в . Рассмотрим время сразу после того, как было выбрано, когда собирается быть выбранным. Независимо от первого выбора (для для ), существует по крайней мере вариантов для и не более из них. выбор даст стоимость края меньше, чем (что делает его дешевым).S π ( i ) π ( i + 1 ) i π ( j ) j ≤ $(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}$

Таким образом, при условии первого выбора вероятность того, что ребро дешево, не превосходит . Таким образом, вероятность того, что все ребра в дешевые, не Поскольку , в есть не менее ребер с . Таким образом, этот продукт не более $i$$\frac{2n^{1-\epsilon/2}}{n-i}$$n/2$$S$|

$$\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