Ungefähre 1d TSP mit linearen Vergleichen?

21

O(nlogn)1+O(nc)cO(n)(maxmin)n(c+1)des ursprünglichen Werts, und verwenden Sie dann die Radix-Sortierung. Aber Modelle mit Rundung haben eine problematische Komplexitätstheorie, und dies führte mich zu der Frage, was ist mit schwächeren Rechenmodellen?

Wie genau kann der eindimensionale TSP in einem linearen Vergleichsbaum-Berechnungsmodell (jeder Vergleichsknoten testet das Vorzeichen einer linearen Funktion der Eingabewerte) durch einen Algorithmus approximiert werden, dessen Zeitkomplexität ? Mit der gleichen Rundungsmethode kann jedes Näherungsverhältnis der Form erreicht werden (durch Verwenden von binären Suchen, um die Rundung durchzuführen, und durch viel gröberes Runden, um sie schnell genug zu machen). Aber ist es möglich, für einige sogar ein Näherungsverhältnis wie zu erreichen ?o(nlogn)n1o(1)O(n1ϵ)ϵ>0

David Eppstein
quelle
Ich bin mit 1D TSP nicht vertraut. Kannst du es definieren?
Tyson Williams
4
@Tyson Williams: Das 1D-Problem mit dem Vertriebspfad für Reisende ist der Spezialfall des euklidischen Problems mit dem Vertriebspfad für Reisende, bei dem alle Städte auf der x-Achse liegen. Oder formal erhalten Sie n reelle Zahlen a_1,…, a_n und Ihr Ziel ist die Ausgabe einer Permutation π: {1,…, n} → {1,…, n}, so dass ∑_ {i = 1} ^ {n - 1} | a_ {π (i)} - a_ {π (i + 1)} | minimiert wird.
Tsuyoshi Ito

Antworten:

10

BEARBEITEN (UPDATE): Die untere Schranke in meiner Antwort unten wurde (durch einen anderen Beweis) in "Zur Komplexität der Annäherung an euklidische Handelsreisetouren und minimale Spannweiten" von Das et al. Algorithmica 19: 447 & ndash; 460 (1997).


ist es möglich, für einige ϵ > sogar ein Näherungsverhältnis wie zu erreichenO(n1ϵ) in o ( n log n ) Zeiteinen vergleichsbasierten Algorithmus?ϵ>0o(nlogn)

Hier ist eine Untergrenze.

Anspruch. Für jedes erfordert jeder vergleichsbasierte n 1 - ϵ -Näherungsalgorithmus im ungünstigsten Fall Ω ( ϵ n log n ) -Vergleiche.ϵ>0n1ϵΩ(ϵnlogn)

Mit "vergleichsbasiert" meine ich jeden Algorithmus, der nur die Eingabe mit binären (True / False) Abfragen abfragt.

Hier ist ein Versuch eines Beweises. Hoffentlich gibt es keine Fehler. FWIW scheint sich die Untergrenze wahrscheinlich auf randomisierte Algorithmen zu erstrecken.


Fixiere ein beliebiges und ein beliebig kleines, aber konstantes ϵ > 0 .nϵ>0

Betrachten Sie nur die "Permutation" -Eingabeinstanzen ( x 1 , x 2 , ... , x n ) , die Permutationen von sindn!(x1,x2,,xn) . Die optimale Lösung für einen solchen Fall kostet n - 1 .[n]n1

Definieren Sie die Kosten einer Permutation zu c ( π ) = i | π ( i + 1 ) - π ( i ) | . Modell des Algorithmus nimmt als Eingang eine Permutation π , Ausgeben eine Permutation π ' , und Zahl Kosten d ( π , π ' ) = cπc(π)=i|π(i+1)π(i)|ππ .d(π,π)=c(ππ)

Definieren Sie als Mindestanzahl von Vergleichen für jeden vergleichsbasierten Algorithmus, um in diesen Fällen ein Konkurrenzverhältnis von n 1 - ϵ zu erzielen . Da opt n - 1 ist , muss der Algorithmus Kosten von höchstens n 2 - ϵ garantieren .Cn1ϵn1n2ϵ

Wir zeigen .CΩ(ϵnlogn)

Definiere so, dass es für jede mögliche Ausgabe π ' der Bruchteil der möglichen Eingaben ist, für die die Ausgabe π ' höchstens n 2 - ϵ kosten würde . Dieser Bruchteil ist unabhängig von π ' .Pππn2ϵπ

auch gleich der Wahrscheinlichkeit, dass für eine zufällige Permutation π ihre Kosten c ( π ) höchstens n 2 - ϵ betragen . (Um zu sehen, warum gilt π ' als Identitätspermutation I. Dann ist P der Anteil der Eingaben, für die d ( π , I ) höchstens n 2 - ϵ ist , aber d ( π , I ) = c ( π ) . )Pπc(π)n2ϵπIPd(π,I)n2ϵd(π,I)=c(π)

Lemma 1 .Clog21/P

Beweis. Beheben Sie jeden Algorithmus, der immer weniger als Vergleiche verwendet. Der Entscheidungsbaum für den Algorithmus hat eine Tiefe von weniger als log 2 1 / P , so dass weniger als 1 / P Blätter vorhanden sind, und für einige Ausgabepermutationen π ' gibt der Algorithmus π ' als Ausgabe für mehr als einen Bruchteil von P aus die Eingänge. Per Definition von P gibt der Ausgang π ' für mindestens einen solchen Eingang Kosten von mehr als n 2 - ϵ . QEDlog21/Plog21/P1/PππPPπn2ϵ

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

Bevor wir den Beweis von Lemma 2 geben, beachten Sie, dass die beiden Lemmas zusammen die Behauptung ergeben:

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

Beweis von Lemma 2. Sei eine zufällige Permutation. Man erinnere sich, dass P gleich der Wahrscheinlichkeit ist, dass seine Kosten c ( π ) höchstens n 2 - ϵ betragen . Angenommen, jedes Paar ( i , i + 1 ) ist eine Kante mit den Kosten | π ( i + 1 ) - π ( i ) | , So c ( π ) ist die Summe der Randkosten.πPc(π)n2ϵ(i,i+1)|π(i+1)π(i)|c(π)

Angenommen, .c(π)n2ϵ

Dann haben für jedes höchstens n 2 - ϵ / q der Kanten q oder mehr gekostet . Nehmen wir an, Kanten, die weniger als q kosten, sind billig .q>0n2ϵ/qqq

Fix . Ersetzen und vereinfachen sind höchstens n 1 - ϵ / 2 der Kanten nicht billig.q=n1ϵ/2n1ϵ/2

Thus, at least nn1ϵ/2n/2 of the edges are cheap. Thus, there is a set S containing n/2 cheap edges.

Anspruch. Für jede gegebene Menge von n / 2 Kanten ist die Wahrscheinlichkeit, dass alle Kanten in S billig sind, höchstens exp ( - Ω ( ϵ nSn/2Sexp(Ω(ϵnlogn)).

Bevor wir die Behauptung beweisen, beachten Sie, dass es das Lemma wie folgt impliziert. Durch die Ansprüche und die naive Union gebunden ist , dass die Wahrscheinlichkeit , eine beliebige es existiert eine solche Menge ist höchstens ( nS

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

Proof of Claim. Choose π by the following process. Choose π(1) uniformly from [n], then choose π(2) uniformly from [n]{π(1)}, then choose π(3) uniformly from [n]{π(1),π(2)}, etc.

(i,i+1)Sπ(i)π(i+1)iπ(j)ji), there are at least ni choices for π(i+1), and at most 2n1ϵ/2 of those choices will give the edge (i,i+1) cost less than n1ϵ/2 (making it cheap).

Thus, conditioned on the first i choices, the probability that the edge is cheap is at most 2n1ϵ/2ni. Thus, the probability that all n/2 edges in S are cheap is at most

(i,i+1)S2n1ϵ/2ni.
Since |S|n/2, there are at least n/4 edges in S with nin/4. Thus, this product is at most
(2n1ϵ/2n/4)n/4  (8nϵ/2)n/4 = exp(O(n)Ω(ϵnlogn)) = exp(Ω(ϵnlogn)).

QED

Neal Young
quelle
6
p.s. I got a request to make this citable, so I put it on arvix.org here.
Neal Young