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

21

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(nlogn)1+O(nc)cO(n)(maxmin)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(nlogn) ? Ta sama metoda zaokrąglania umożliwia uzyskanie dowolnego współczynnika aproksymacji postaci n1o(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(n1ϵ) dla niektórych ϵ>0 ?

David Eppstein
źródło
Nie jestem zaznajomiony z 1D TSP. Czy potrafisz to zdefiniować?
Tyson Williams,
4
@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,

Odpowiedzi:

10

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?ϵ > 0 o ( n log n )O(n1ϵ)ϵ>0o(nlogn)

Nie. Oto dolna granica.

Roszczenie. Dla każdego każdy algorytm aproksymacji oparty na porównaniu wymaga w najgorszym przypadku porównań .n 1 - ϵ Ω ( ϵ n log n )ϵ>0n1ϵΩ(ϵnlogn)

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 .ϵ > 0nϵ>0

Rozważ tylkoinstancje wejściowe „permutacja” które są permutacjami . Optymalne rozwiązanie dla każdego takiego przypadku ma koszt .( x 1 , x 2 , , x n ) [ n ] n - 1n!(x1,x2,,xn)[n]n1

Zdefiniuj koszt permutacji jako. Modeluj algorytm jako przyjmujący permutację , wyprowadzający permutację i płacący koszt .cππ π d ( π , π ) = c ( π π )c(π)=i|π(i+1)π(i)|ππd(π,π)=c(ππ)

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 .n 1 - ϵ n - 1 n 2 - ϵCn1ϵn1n2ϵ

Pokażemy .CΩ(ϵnlogn)

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 .π π n 2 - ϵ π Pππn2ϵπ

π c ( π ) n 2P 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 .)πc(π) π IPd(π,I) n 2 - ϵ d(π,I)=c(π)n2ϵπIPd(π,I)n2ϵd(π,I)=c(π)

Lemat 1. .Clog21/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 OKAZANIAlog21/P1 / P π π P P π n 2 - ϵlog21/P1/PππPPπn2ϵ

Lemma 2. .Pexp(Ω(ϵnlogn))

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

C  log21P = log2exp(Ω(ϵnlogn)) = Ω(ϵnlogn).

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.P c ( π )πPc(π) ( i , i + 1 ) | π ( i + 1 ) - π ( i ) | c ( π )n2ϵ(i,i+1)|π(i+1)π(i)|c(π)

Załóżmy, że .c(π)n2ϵ

Następnie dla dowolnego najwyżej krawędzi ma koszt lub więcej. Powiedz, że krawędzie kosztują mniej niż są tanie .n 2 - ϵ / q q qq>0n2ϵ/qqq

Napraw . Zastępując i upraszczając, najwyżej krawędzi nie są tanie. n 1 - ϵ / 2q=n1ϵ/2n1ϵ/2

Tak więc co najmniej krawędzi jest tanie. Tak więc istnieje zestaw zawierający tanich krawędzi.S n / 2nn1ϵ/2n/2Sn/2

Roszczenie. Dla danego zbioru o krawędzi, prawdopodobieństwo, że wszystkie krawędzie w są tanie, co najwyżej .n / 2 S exp ( - Ω ( ϵ n log n ) )Sn/2Sexp(Ω(ϵnlogn))

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 ( nSexp

(nn/2)exp(Ω(ϵnlogn))  2nexp(Ω(ϵnlogn))
  exp(O(n)Ω(ϵnlogn))  exp(Ω(ϵnlogn)).

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.π ( 1 ) [ n ] π ( 2 )ππ(1)[n]π(2)π ( 3 ) [ n ] - { π ( 1 ) , π ( 2 ) }[n]{π(1)}π(3)[n]{π(1),π(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ą).S π ( i ) π ( i + 1(i,i+1)Sπ(i)i π ( j ) j i n - i π ( i + 1 ) 2 n 1 - ϵ / 2 ( i , i + 1 ) n 1 - ϵ / 2π(i+1)iπ(j)jiniπ(i+1)2n1ϵ/2(i,i+1)n1ϵ/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 2 n 1 - ϵ / 2i n/2S(i,i+1)S2n 1 - ϵ / 22n1ϵ/2nin/2S| S| n/2n/4Sn-in/4(2n 1 - ϵ / 2

(i,i+1)S2n1ϵ/2ni.
|S|n/2n/4Snin/4
(2n1ϵ/2n/4)n/4  (8nϵ/2)n/4 = exp(O(n)Ω(ϵnlogn)) = exp(Ω(ϵnlogn)).

CO BYŁO DO OKAZANIA

Neal Young
źródło
6
ps Dostałem prośbę o uczynienie tego cytowalnym, więc umieściłem go tutaj na arvix.org .
Neal Young