Näherungsalgorithmen für metrische TSP

Es ist bekannt, dass der metrische TSP innerhalb von approximiert werden kann und nicht besser als 123 approximiert werden kann$1.5$ in polynomialer Zeit. Ist etwas über das Finden von Approximationslösungen in exponentieller Zeit bekannt (z. B. weniger als2nSchritte mit nur polynomialem Raum)? ZB in welcher Zeit und an welchem ​​Ort können wir eine Tour finden, deren Entfernung höchstens1,1×OPTbeträgt?$123\over 122$$2^n$$1.1\times OPT$

Ich habe das Problem untersucht und die bekanntesten Algorithmen für TSP gefunden.

$n$$M$$poly(n, \log M)$

1. Genaue Algorithmen für TSP

1.1. Allgemeine ATSP

$M2^{n-\Omega(\sqrt{n/\log (Mn)})}$$exp$

$2^n$$2^n$

$4^n n^{\log n}$$poly$

$2^{2n-t} n^{\log(n-t)}$$2^t$$t=n,n/2,n/4,\ldots$

$O^*(T^n)$$O^*(S^n)$$\sqrt2<S<2$$TS<4$

$2^n\times M$

$2^n\times M$$M$

$2^n$

1.2. Sonderfälle von TSP

$1.657^n\times M$

$(2-\epsilon)^n$$\epsilon$

$(2-\epsilon)^n$$poly$$\epsilon$

$1.251^n$$poly$

$1.890^n$$poly$$4$

$1.733^n$$4$

$1.657^n$$poly$

$(2-\epsilon)^n$$d^n$$d$

2. Approximationsalgorithmen für TSP

2.1. General TSP

Kann nicht innerhalb einer berechenbaren Polynomzeitfunktion approximiert werden, es sei denn, P = NP ( Sahni, Gonzalez ).

2.2. Metrischer TSP

$3 \over 2$

Kann nicht mit einem Verhältnis besser als angenähert werden$123\over 122$

2.3. Grafik TSP

$7\over5$

2.4. (1,2) -TSP

MAX-SNP schwer ( Papadimitriou, Yannakakis ).

$8 \over 7$

2.5. TSP in Metriken mit begrenzter Dimension

PTAS für TSP in einem festdimensionalen euklidischen Raum ( Arora ; Mitchell ).

$\log{n}$

PTAS für TSP in Metriken mit begrenzter Verdopplungsdimension ( Bartal, Gottlieb, Krauthgamer ).

2.6. ATSP mit gerichteter Dreieckungleichung

$O(1)$

Kann nicht mit einem Verhältnis besser als angenähert werden$75\over 74$

2.7. TSP in Grafiken mit verbotenen Minderjährigen

Lineare Zeit PTAS ( Klein ) für TSP in planaren Graphen.

PTAS für minderjährige Graphen ( Demaine, Hajiaghayi, Kawarabayashi ).

$22\frac{1}{2}$

$O(\frac{\log g}{\log\log g})$$g$

2.8. MAX-TSP

$7\over9$

$7\over8$

$3\over4$

$35\over44$

2.9. Exponential-Zeit-Approximationen

Es ist möglich, zu berechnen$(1+\epsilon)$$2^{(1-\epsilon/2)n}$$\epsilon\le \frac{2}{5}$$4^{(1-\epsilon/2)n} n^{\log n}$$\epsilon \leq \frac{2}{3}$

Für Ergänzungen und Anregungen wäre ich dankbar.

$O^*(1.932^n)$$O^*(2^n)$$n$$(1+\epsilon)$$O^*(2^{(1-\epsilon/2)n})$$\epsilon \le 2/5$

Nicolas Boria, Nicolas Bougeois, Bruno Escoffier, Vangelis Th. Paschos: Exponentielle Approximationsschemata für einige Graphprobleme. Online verfügbar .

$\alpha$$\beta$$\alpha < \beta$$\gamma$$\alpha, \beta]$$\gamma$$\theta$$\gamma$$2^{n^{O(\theta)}}$$\gamma$(zumindest im konstanten Faktorbereich) Verbesserungen des Approximationsverhältnisses auch bei subexponentieller Zeit. Es gibt mehrere Probleme, bei denen das beste bekannte Härteergebnis durch eine ineffiziente Reduktion von SAT erzielt wird, dh, das Härteergebnis unterliegt einer schwächeren Annahme, wie z. B. NP, das nicht in der Quasipolynomzeit enthalten ist. In solchen Fällen kann man eine bessere Annäherung in subexponentieller Zeit erhalten. Das einzige, von dem ich weiß, ist das Steiner-Baum-Problem. Ein kürzlich bekanntes Ergebnis ist das von Arora-Barak-Steurer über einen subexponentiellen Zeitalgorithmus für einzigartige Spiele: Die Schlussfolgerung, die wir aus diesem Ergebnis ziehen, ist, dass, wenn UGC wahr ist, die Reduktion von SAT zu UGC etwas sein muss ineffizient, das heißt, die Größe der Instanz von UGC, die aus der SAT-Formel erhalten wird, muss in gewisser Weise mit den Parametern wachsen.

Der beste TL für gewichtete, begrenzte Gattungsgraphen ist http://erikdemaine.org/papers/ContractionTSP_Combinatorica/ .