Algoritma pendekatan untuk Metric TSP

Diketahui bahwa metrik TSP dapat diperkirakan dalam dan tidak dapat diperkirakan lebih baik dari $1.5$ dalam waktu polinomial. Apakah sesuatu yang diketahui tentang menemukan solusi pendekatan dalam waktu eksponensial (misalnya, kurang dari2nlangkah dengan hanya ruang polinomial)? Misalnya dalam waktu dan ruang apa kita dapat menemukan tur yang jaraknya paling jauh1.1×OPT?$123\over 122$$2^n$$1.1\times OPT$

Saya telah mempelajari masalahnya dan saya menemukan algoritma yang paling terkenal untuk TSP.

$n$ adalah jumlah simpul,$M$ adalah bobot tepi maksimal. Semua batas diberikan hingga faktor polinom dari ukuran input ($poly(n, \log M)$ ). Kami menunjukkan Asymmetric TSP oleh ATSP.

1. Algoritma Tepat untuk TSP

1.1. ATSP umum

$M2^{n-\Omega(\sqrt{n/\log (Mn)})}$waktu dan$exp$-ruang (Björklund).

$2^n$ waktu dan$2^n$ spasi (Bellman;Held, Karp).

$4^n n^{\log n}$ waktu dan$poly$ -space (Gurevich, Shelah;Björklund, Husfeldt).

$2^{2n-t} n^{\log(n-t)}$ waktu dan$2^t$ ruang untuk$t=n,n/2,n/4,\ldots$ (Koivisto, Parviainen).

$O^*(T^n)$ waktu dan$O^*(S^n)$ ruang untuk$\sqrt2<S<2$dengan$TS<4$(Koivisto, Parviainen).

$2^n\times M$ waktu dan ruang-poli (Lokshtanov, Nederlof).

$2^n\times M$ ruang dan waktu$M$ (Kohn, Gottlieb, Kohn;Karp;Bax, Franklin).

$2^n$

1.2. Kasus Khusus 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. Algoritma Perkiraan untuk TSP

2.1. TSP umum

Tidak dapat diperkirakan dalam fungsi waktu komputasi polinomial apa pun kecuali P = NP ( Sahni, Gonzalez ).

2.2. TSP metrik

$3 \over 2$

$123\over 122$

2.3. TSP grafis

$7\over5$

2.4. (1,2) -TSP

MAX-SNP keras ( Papadimitriou, Yannakakis ).

$8 \over 7$

2.5. TSP dalam Metrik dengan Dimensi Terbatas

PTAS untuk TSP dalam ruang Euclidean dimensi-tetap ( Arora ; Mitchell ).

$\log{n}$

PTAS untuk TSP dalam metrik dengan dimensi penggandaan terikat ( Bartal, Gottlieb, Krauthgamer ).

2.6. ATSP dengan Directed Triangle Inequality

$O(1)$

$75\over 74$

2.7. TSP dalam Grafik dengan Anak Terlarang

PTAS ( Klein ) waktu linier untuk TSP dalam Grafik Planar.

PTAS untuk grafik kecil-gratis ( 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. Perkiraan Waktu-Eksponensial

$(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}$

Saya akan berterima kasih atas penambahan dan saran.

$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: Skema aproksimasi eksponensial untuk beberapa masalah grafik. Tersedia online .

$\alpha$$\beta$$\alpha < \beta$$\gamma$$\alpha, \beta]$$\gamma$$\theta$$\gamma$$2^{n^{O(\theta)}}$$\gamma$(setidaknya dalam kisaran faktor konstan) melihat peningkatan dalam rasio perkiraan bahkan ketika diberikan waktu sub-eksponensial. Ada beberapa masalah di mana hasil kekerasan terbaik yang diketahui adalah melalui pengurangan yang tidak efisien dari SAT, yaitu, hasil kekerasan berada di bawah asumsi yang lebih lemah seperti NP yang tidak terkandung dalam waktu kuasi-polinomial. Dalam kasus seperti itu, orang mungkin mendapatkan perkiraan yang lebih baik dalam waktu sub-eksponensial. Satu-satunya yang saya tahu adalah masalah pohon kelompok Steiner. Hasil yang terkenal baru-baru ini adalah salah satu dari Arora-Barak-Steurer pada algoritma sub-eksponensial-waktu untuk game unik: kesimpulan yang kami ambil dari hasil ini adalah bahwa jika UGC benar maka pengurangan dari SAT ke UGC harus menjadi apa tidak efisien, yaitu, ukuran instance UGC yang diperoleh dari rumus SAT harus tumbuh dengan parameter dengan cara tertentu.

Tsp terbaik untuk grafik genus terikat tertimbang adalah http://erikdemaine.org/papers/ContractionTSP_Combinatorica/ .