Perkiraan TSP 1d dengan perbandingan linear?

Masalah jalur penjual keliling satu dimensi, tentu saja, sama dengan penyortiran, dan dengan demikian dapat diselesaikan dengan tepat dengan perbandingan dalam waktu , tetapi dirumuskan sedemikian rupa sehingga perkiraan serta tepat solusi masuk akal. Dalam model perhitungan di mana input adalah bilangan real, dan pembulatan ke bilangan bulat dimungkinkan, mudah untuk memperkirakan dalam faktor , untuk konstanta apa pun , pada waktu : cari min dan maks, bulatkan semuanya ke angka dalam jarak dari nilai aslinya, lalu gunakan jenis radix. Tetapi model dengan pembulatan memiliki teori kompleksitas yang bermasalah dan ini membuat saya bertanya-tanya, bagaimana dengan model komputasi yang lebih lemah?$O(n\log n)$$1+O(n^{-c})$$c$$O(n)$$(\max-\min)n^{-(c+1)}$

Jadi, seberapa akurat TSP satu dimensi dapat diperkirakan, dalam model perbandingan pohon linear perhitungan (setiap node perbandingan menguji tanda fungsi linear dari nilai input), dengan algoritma yang kompleksitas waktunya adalah ? Metode pembulatan yang sama memungkinkan setiap rasio perkiraan bentuk dapat dicapai (dengan menggunakan pencarian biner untuk melakukan pembulatan, dan pembulatan jauh lebih kasar untuk membuatnya cukup cepat). Tetapi apakah mungkin untuk mencapai bahkan rasio perkiraan seperti untuk beberapa ?$o(n\log n)$$n^{1-o(1)}$$O(n^{1-\epsilon})$$\epsilon>0$

EDIT (PEMBARUAN): Batas bawah dalam jawaban saya di bawah ini telah terbukti (dengan bukti berbeda) dalam "Tentang kerumitan perkiraan tur penjual keliling Euclidean dan pohon merentang minimum", oleh Das et al; Algorithmica 19: 447-460 (1997).

---

apakah mungkin untuk mencapai bahkan rasio perkiraan seperti untuk beberapa ϵ > 0 dalam waktu o ( n log n ) menggunakan algoritma berbasis perbandingan?$O(n^{1-\epsilon})$$\epsilon>0$$o(n\log n)$

Tidak. Ini batas bawah.

Klaim. Untuk , setiap perbandingan berbasis n 1 - ϵ algoritma-aproximation membutuhkan perbandingan Ω ( ϵ n log n ) dalam kasus terburuk.$\epsilon>0$$n^{1-\epsilon}$$\Omega(\epsilon n\log n)$

Dengan "berbasis perbandingan" maksud saya algoritma apa pun yang hanya menanyakan input dengan permintaan biner (Benar / Salah).

Ini adalah upaya untuk membuktikan. Semoga tidak ada kesalahan. FWIW batas bawah tampaknya cenderung meluas ke algoritma acak.

---

Perbaiki sembarang dan sembarang kecil tetapi konstan ϵ > 0 .$n$$\epsilon>0$

Anggap saja instance input "permutasi" ( x 1 , x 2 , ... , x n ) yang merupakan permutasi dari [ n ] . Solusi optimal untuk setiap instance tersebut memiliki biaya n - 1 .$n!$$(x_1,x_2,\ldots,x_n)$$[n]$$n-1$

Tentukan biaya permutasi menjadi c ( π ) = ∑ i | π ( i + 1 ) - π ( i ) | . Model algoritma sebagai mengambil input permutasi π , mengeluarkan permutasi π ′ , dan membayar biaya d ( π , π ′ ) = c ( π ′ ∘ π ) .$\pi$$c(\pi) = \sum_i |\pi(i+1) - \pi(i)|$$\pi$$\pi'$$d(\pi,\pi') = c(\pi'\circ \pi)$

Tentukan sebagai jumlah minimum perbandingan untuk setiap algoritma berbasis perbandingan untuk mencapai rasio kompetitif n 1 - ϵ pada contoh-contoh ini. Karena opt adalah n - 1 , algoritma harus menjamin biaya paling banyak n 2 - ϵ .$C$$n^{1-\epsilon}$$n-1$$n^{2-\epsilon}$

Kami akan menunjukkan .$C\ge \Omega(\epsilon n\log n)$

Tentukan sebagai, untuk kemungkinan output π ′ , fraksi dari kemungkinan input yang mana output π ′ akan mencapai biaya paling banyak n 2 - ϵ . Fraksi ini tidak bergantung pada π ′ .$P$$\pi'$$\pi'$$n^{2-\epsilon}$$\pi'$

juga sama dengan probabilitas bahwa, untuk permutasi acak π , biayanya c ( π ) paling banyak n 2 - ϵ . (Untuk melihat alasannya, anggap π ′ sebagai permutasi identitas I. Kemudian P adalah fraksi input yang paling banyak d ( π , I ) paling banyak n 2 - ϵ , tetapi d ( π , I ) = c ( π ) . )$P$$\pi$$c(\pi)$$n^{2-\epsilon}$$\pi'$$I$$P$$d(\pi,I)$$n^{2-\epsilon}$$d(\pi,I) = c(\pi)$

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

Bukti. Perbaiki semua algoritma yang selalu menggunakan perbandingan kurang dari Pohon keputusan untuk algoritma memiliki kedalaman kurang dari log 2 1 / P , jadi ada kurang dari 1 / P daun, dan, untuk beberapa permutasi output π ′ , algoritma memberikan π ′ sebagai output untuk lebih dari fraksi P dari input. Menurut definisi P , untuk setidaknya satu input seperti itu, output π ′ memberikan biaya lebih dari n 2 - ϵ . QED$\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))$

Sebelum kami memberikan bukti Lemma 2, perhatikan bahwa kedua lemma bersama-sama memberikan klaim:

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

---

Bukti Lemma 2. Biarkan menjadi permutasi acak. Ingat bahwa P sama dengan probabilitas bahwa biayanya c ( π ) paling banyak n 2 - ϵ . Katakanlah bahwa setiap pasangan ( i , i + 1 ) adalah tepi dengan biaya | π ( i + 1 ) - π ( i ) | , jadi c ( π ) adalah jumlah dari biaya tepi.$\pi$$P$$c(\pi)$$n^{2-\epsilon}$$(i,i+1)$$|\pi(i+1)-\pi(i)|$$c(\pi)$

Misalkan .$c(\pi) \le n^{2-\epsilon}$

Kemudian, untuk apa pun , paling banyak n 2 - ϵ / q pada tepi memiliki biaya q atau lebih. Katakan bahwa tepi biaya kurang dari q yang murah .$q>0$$n^{2-\epsilon}/q$$q$$q$

Perbaiki . Mengganti dan menyederhanakan, paling tidak n 1 - ϵ / 2 dari tepi tidak murah.$q=n^{1-\epsilon/2}$$n^{1-\epsilon/2}$

Jadi, paling tidak tepinya murah. Jadi, ada himpunan S yang berisi n / 2 tepi murah.$n - n^{1-\epsilon/2} \ge n/2$$S$$n/2$

Klaim. Untuk setiap himpunan dari n / 2 edge, probabilitas bahwa semua edge di S adalah paling murah exp ( - Ω ( ϵ n log n ) ) .$S$$n/2$$S$$\exp(-\Omega(\epsilon n \log n))$

Sebelum kami membuktikan klaim, perhatikan bahwa itu menyiratkan lemma sebagai berikut. Dengan klaim, dan ikatan naif terikat, probabilitas bahwa ada yang ada set paling banyak ($S$≤exp(O(n)-Ω(ϵnlogn))≤exp(-Ω(ϵnlogn))

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

---

Bukti Klaim. Pilih dengan proses berikut. Pilih π ( 1 ) secara seragam dari [ n ] , lalu pilih π ( 2 ) secara seragam dari [ n ] - { π ( 1 ) } , lalu pilih π ( 3 ) secara seragam dari [ n ] - { π ( 1 ) , π ( 2 ) } , dll.$\pi$$\pi(1)$$[n]$$\pi(2)$$[n] - \{\pi(1)\}$$\pi(3)$$[n]-\{\pi(1),\pi(2)\}$

Pertimbangkan setiap tepi di S . Pertimbangkan waktu tepat setelah π ( i ) telah dipilih, ketika π ( i + 1 ) akan dipilih. Terlepas dari pilihan i pertama (untuk π ( j ) untuk j ≤ i ), setidaknya ada n - i pilihan untuk π ( i + 1 ) , dan paling banyak 2 n $(i,i+1)$$S$$\pi(i)$$\pi(i+1)$$i$$\pi(j)$$j\le i$$n-i$$\pi(i+1)$ dari orang-orang pilihan akan memberikan tepi(i,i+1) biaya kurang dari n 1 - ε / 2 (menjadikannya murah).$2n^{1-\epsilon/2}$$(i,i+1)$$n^{1-\epsilon/2}$

Dengan demikian, dikondisikan pada pilihan pertama , probabilitas bahwa tepi murah paling banyak 2 n 1 - ϵ /$i$ . Dengan demikian, probabilitas bahwa semua tepin/2diSadalah paling murah ∏(i,i+1)∈S2n 1 - ϵ /$\frac{2n^{1-\epsilon/2}}{n-i}$$n/2$$S$ Sejak| S| ≥n/2, setidaknya adan/4tepi diS dengann-i≥n/4. Dengan demikian, produk ini paling banyak (2n 1 - ϵ /

$$\prod_{(i,i+1)\in S} \frac{2n^{1-\epsilon/2}}{n-i}.$$ $|S|\ge n/2$$n/4$$S$$n-i\ge n/4$ $$\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)).$$

QED