Menyortir titik sedemikian rupa sehingga jarak Euclidean minimal antara titik berurutan akan dimaksimalkan

Diberikan satu set poin dalam ruang Cartesian 3D, saya mencari algoritma yang akan mengurutkan poin-poin ini, sehingga jarak Euclidean minimal antara dua titik berturut-turut akan dimaksimalkan.

Ini juga akan bermanfaat jika algoritma memiliki kecenderungan menuju jarak Euclidean rata-rata yang lebih tinggi antara titik-titik yang berurutan.

graph-algorithms cg.comp-geom optimization Lior Kogan
sumber

Crossposted , motivasi .

Jukka Suomela

Kedengarannya seperti versi maksimalisasi bottleneck TSP . Atau versi bottleneck dari masalah jalur terpanjang . Apakah itu mempunyai nama?

Jukka Suomela

Saya akan merekomendasikan menggunakan heuristik gonzalez k-clustering (strategi serakah). tanpa memikirkan ini sepenuhnya, sepertinya ia harus menghasilkan 2-aproksimasi?

Suresh Venkat

Sayangnya, seperti yang dinyatakan, Gonzalez tidak akan memberikan jawaban yang baik (pertimbangkan poin (-100,0), (99,0) dan (100,0)). Jika kita mulai dari titik yang salah (-100,0) misalnya, kita mendapatkan jawaban yang buruk. Mungkin saja menjalankan gonzalez dari setiap titik dan mengambil jawaban terbaik akan berhasil.

Suresh Venkat

Jawaban:

ETA: Segala sesuatu di bawah ini ada dalam makalah " On the maksimum scatter TSP ", Arkin et al, SODA 1997.

Saya tidak tahu tentang jawaban yang pasti, tapi inilah pendekatan lain yang sedikit berbeda dari saran Suresh tentang pengelompokan Gonzalez:

$n$ $p$ $n-1$ $d(p,q)$ $p$ $n/2$

$n/2 + 1$ $p$ $d(p,q)$ $2d(p,q)$

Ini akan bekerja di ruang metrik apa pun, dan memberikan rasio perkiraan optimal di antara algoritma yang bekerja di ruang metrik apa pun. Karena, jika Anda dapat memperkirakan lebih baik daripada dalam faktor dua maka Anda dapat menyelesaikan masalah siklus Hamilton dengan tepat, dengan mengurangi grafik input ke masalah siklus Hamilton ke dalam ruang metrik dengan jarak 2 untuk setiap tepi grafik dan jarak 1 untuk setiap non -tepi.

Mungkin dengan hati-hati Anda dapat memijat ini menjadi algoritma perkiraan untuk jalur, bukan siklus.

David Eppstein
sumber

Apakah ada alasan untuk percaya bahwa tidak ada PTAS dalam kasus Euclidean?

Jukka Suomela

Tidak ada alasan yang saya ketahui. Tetapi metode PTAS biasa untuk masalah desain jaringan Euclidean hanya bekerja untuk minimalisasi, bukan maksimalisasi.

David Eppstein

Satu pengecualian yang saya tahu adalah kertas Chen dan Har-Peled pada PTAS untuk Orienteering di pesawat. Ini adalah masalah maksimalisasi.

Chandra Chekuri

Kami mengunggah pracetak yang membahas pertanyaan ini, yaitu memberikan PTAS untuk max scatter TSP dalam kasus euclidean. arxiv.org/abs/1512.02963 (László Kozma, Tobias Mömke: A PTAS untuk Euclidean Maximum Scatter TSP)

László Kozma

Kami mengunggah pracetak yang membahas pertanyaan ini, yaitu memberikan PTAS untuk max scatter TSP dalam kasus euclidean. http://arxiv.org/abs/1512.02963 (László Kozma, Tobias Mömke: A PTAS untuk Euclidean Maximum Scatter TSP)

László Kozma
sumber