Przybliżony 1d TSP z porównaniami liniowymi?

Jednowymiarowy problem ścieżki sprzedawcy podróży jest oczywiście tym samym, co sortowanie, a zatem można go rozwiązać dokładnie przez porównanie w czasie , ale sformułowano go w taki sposób, aby przybliżenie, a także dokładne rozwiązanie ma sens. W modelu obliczeń, w którym dane wejściowe są liczbami rzeczywistymi i możliwe jest zaokrąglanie do liczb całkowitych, łatwo jest aproksymować do współczynnika , dla dowolnej stałej , w czasie : znajdź min i maks, zaokrąglij wszystko do liczby w odległości od pierwotnej wartości, a następnie użyj sortowania radix. Ale modele z zaokrąglaniem mają problematyczną teorię złożoności, co doprowadziło mnie do zastanowienia się, a co ze słabszymi modelami obliczeń? $O(n\log n)$ $1+O(n^{-c})$ $c$ $O(n)$ $(\max-\min)n^{-(c+1)}$

Jak dokładnie można aproksymować jednowymiarowy TSP w liniowym modelu drzewa porównawczego obliczeń (każdy węzeł porównawczy testuje znak funkcji liniowej wartości wejściowych) za pomocą algorytmu, którego złożoność czasowa wynosi $o(n\log n)$ ? Ta sama metoda zaokrąglania umożliwia uzyskanie dowolnego współczynnika aproksymacji postaci $n^{1-o(1)}$ (za pomocą wyszukiwania binarnego w celu wykonania zaokrąglenia i zaokrąglenia znacznie bardziej zgrubnie, aby było wystarczająco szybkie). Ale czy możliwe jest osiągnięcie nawet współczynnika aproksymacji takiego jak $O(n^{1-\epsilon})$ dla niektórych $\epsilon>0$ ?

— David Eppstein
źródło

Nie jestem zaznajomiony z 1D TSP. Czy potrafisz to zdefiniować?

— Tyson Williams,

@Tyson Williams: Problem ścieżki sprzedawcy 1D jest szczególnym przypadkiem problemu ścieżki sprzedawcy podróży Euclide, gdzie wszystkie miasta znajdują się na osi X. Lub formalnie otrzymujesz n liczb rzeczywistych a_1,…, a_n, a Twoim celem jest uzyskanie permutacji π: {1,…, n} → {1,…, n} takiej, że ∑_ {i = 1} ^ {n − 1} | a_ {π (i)} - a_ {π (i + 1)} | jest zminimalizowane.

— Tsuyoshi Ito,

EDYCJA (AKTUALIZACJA): Dolną granicę w mojej odpowiedzi poniżej udowodniono (innym dowodem) w „O złożoności przybliżania podróży euklidesowych sprzedawcom i minimalnym drzewom spinającym”, autorstwa Das i in .; Al Algorytmica 19: 447-460 (1997).

czy możliwe jest osiągnięcie nawet współczynnika aproksymacji takiego jak dla pewnego za przy użyciu algorytmu opartego na porównaniu? $O(n^{1-\epsilon})$ $\epsilon>0$ $o(n\log n)$

Nie. Oto dolna granica.

Roszczenie. Dla każdego każdy algorytm aproksymacji oparty na porównaniu wymaga w najgorszym przypadku porównań . $\epsilon>0$ $n^{1-\epsilon}$ $\Omega(\epsilon n\log n)$

Pod pojęciem „na podstawie porównania” rozumiem dowolny algorytm, który wysyła zapytania tylko do danych wejściowych za pomocą zapytań binarnych (prawda / fałsz).

Oto próba dowodu. Mam nadzieję, że nie ma błędów. FWIW wydaje się, że dolna granica rozciąga się na algorytmy losowe.

Skoryguj i dowolnie mały, ale ciągłego . $n$ $\epsilon>0$

Rozważ tylkoinstancje wejściowe „permutacja” które są permutacjami . Optymalne rozwiązanie dla każdego takiego przypadku ma koszt . $n!$ $(x_1,x_2,\ldots,x_n)$ $[n]$ $n-1$

Zdefiniuj koszt permutacji jako. Modeluj algorytm jako przyjmujący permutację , wyprowadzający permutację i płacący koszt . $\pi$ $c(\pi) = \sum_i |\pi(i+1) - \pi(i)|$ $\pi$ $\pi'$ $d(\pi,\pi') = c(\pi'\circ \pi)$

Zdefiniuj jako minimalną liczbę porównań dla dowolnego algorytmu opartego na porównaniu, aby osiągnąć współczynnik konkurencyjny w tych przypadkach. Ponieważ opt ma wartość , algorytm musi gwarantować koszt co najwyżej . $C$ $n^{1-\epsilon}$ $n-1$ $n^{2-\epsilon}$

Pokażemy . $C\ge \Omega(\epsilon n\log n)$

Zdefiniuj aby dla każdego możliwego wyjścia był ułamek możliwych nakładów, dla których wyjście osiągnęłoby koszt co najwyżej . Ta część jest niezależna od . $P$ $\pi'$ $\pi'$ $n^{2-\epsilon}$ $\pi'$

$P$ równa się również prawdopodobieństwu, że dla losowej permutacji jego koszt wynosi najwyżej . (Aby zobaczyć dlaczego, weź jako permutację tożsamości Następnie jest ułamkiem danych wejściowych, dla których co najwyżej , ale .) $\pi$ $c(\pi)$ $n^{2-\epsilon}$ $\pi'$ $I$ $P$ $d(\pi,I)$ $n^{2-\epsilon}$ $d(\pi,I) = c(\pi)$

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

Dowód. Napraw dowolny algorytm, który zawsze używa mniej niż porównań. Drzewo decyzyjne algorytmu ma głębokość mniejszą niż , więc jest mniej niż liści, a dla niektórych permutacji wyjściowych algorytm podaje jako wyjście dla więcej niż ułamek nakładów. Z definicji , dla co najmniej jednego takiego wejścia, wynik daje koszt większy niż . CO BYŁO DO OKAZANIA $\log_2 1/P$ $\log_2 1/P$ $1/P$ $\pi'$ $\pi'$ $P$ $P$ $\pi'$ $n^{2-\epsilon}$

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

Zanim podamy dowód na Lemat 2, zauważ, że dwa lematy razem dają roszczenie:

C \geq \log_{2} \frac{1}{P} = \log_{2} \exp (Ω (ϵ n \log n)) = Ω (ϵ n \log n) .

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

Dowód lematu 2. Niech będzie przypadkową permutacją. Przypomnijmy, że równa się prawdopodobieństwu, że jego koszt wynosi najwyżej . Powiedz, że każda para jest przewagą kosztu, więc jest sumą kosztów brzegowych. $\pi$ $P$ $c(\pi)$ $n^{2-\epsilon}$ $(i,i+1)$ $|\pi(i+1)-\pi(i)|$ $c(\pi)$

Załóżmy, że . $c(\pi) \le n^{2-\epsilon}$

Następnie dla dowolnego najwyżej krawędzi ma koszt lub więcej. Powiedz, że krawędzie kosztują mniej niż są tanie . $q>0$ $n^{2-\epsilon}/q$ $q$ $q$

Napraw . Zastępując i upraszczając, najwyżej krawędzi nie są tanie. $q=n^{1-\epsilon/2}$ $n^{1-\epsilon/2}$

Tak więc co najmniej krawędzi jest tanie. Tak więc istnieje zestaw zawierający tanich krawędzi. $n - n^{1-\epsilon/2} \ge n/2$ $S$ $n/2$

Roszczenie. Dla danego zbioru o krawędzi, prawdopodobieństwo, że wszystkie krawędzie w są tanie, co najwyżej . $S$ $n/2$ $S$ $\exp(-\Omega(\epsilon n \log n))$

Zanim udowodnimy to twierdzenie, zwróć uwagę, że sugeruje to następujący lemat. Według twierdzenia i naiwnego związku, prawdopodobieństwo istnienia takiego zestawu wynosi co najwyżej $S$

(\binom{n}{n / 2}) \exp (- Ω (ϵ n \log n)) \leq 2^{n} \exp (- Ω (ϵ n \log n))

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

\leq \exp (O (n) - Ω (ϵ n \log n)) \leq \exp (- Ω (ϵ n \log n)) .

$~\le~ \exp(O(n) -\Omega(\epsilon n \log n)) ~\le~ \exp(-\Omega(\epsilon n \log n)).$

Dowód roszczenia. Wybierz w następujący sposób. Wybierz jednolicie z , następnie wybierz jednolicie z , a następnie wybierz jednolicie z itd. $\pi$ $\pi(1)$ $[n]$ $\pi(2)$ $[n] - \{\pi(1)\}$ $\pi(3)$ $[n]-\{\pi(1),\pi(2)\}$

Rozważmy brzeg w . Rozważ czas tuż po wybraniu , kiedy zostanie wybrany . Niezależnie od pierwszych wyborów (dla dla ), istnieje co najmniej wybór dla , a najwyżej z nich wybory dadzą przewagę mniejszą niż (co czyni ją tanią). $(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}$

Zatem, zależnie od pierwszych wyborów , prawdopodobieństwo, że krawędź jest tania, wynosi najwyżej . Zatem prawdopodobieństwo, że wszystkie zbocza w są tanie, wynosi co najwyżej Od czasu , w jest co najmniej krawędzi z . Tak więc ten produkt jest co najwyżej $i$ $\frac{2n^{1-\epsilon/2}}{n-i}$ $n/2$ $S$

\prod_{(i, i + 1) \in S} \frac{2 n^{1 - ϵ / 2}}{n - i} .

$\prod_{(i,i+1)\in S} \frac{2n^{1-\epsilon/2}}{n-i}.$

| S | \geq n / 2

$|S|\ge n/2$

n / 4

$n/4$

S

$S$

n - i \geq n / 4

$n-i\ge n/4$

(\frac{2 n^{1 - ϵ / 2}}{n / 4})^{n / 4} \leq (8 n^{- ϵ / 2})^{n / 4} = \exp (O (n) - Ω (ϵ n \log n)) = \exp (- Ω (ϵ n \log n)) .

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

CO BYŁO DO OKAZANIA

— Neal Young
źródło

ps Dostałem prośbę o uczynienie tego cytowalnym, więc umieściłem go tutaj na arvix.org .

— Neal Young