Aplikasi Teoritis untuk Algoritma Perkiraan

Akhir-akhir ini saya mulai mencari algoritma perkiraan untuk masalah NP-hard dan saya bertanya-tanya tentang alasan teoritis untuk mempelajarinya. (Pertanyaannya tidak dimaksudkan sebagai peradangan - saya hanya ingin tahu).

Beberapa teori yang benar-benar indah telah keluar dari studi tentang algoritma aproksimasi - hubungan antara teorema PCP dan kekerasan aproksimasi, dugaan UGC, algoritma aproksimasi Goeman-Williamson, dll.

Saya bertanya-tanya tentang titik mempelajari algoritma aproksimasi untuk masalah seperti Travelling Salesman, Asymmetric Travelling Salesman dan varian lainnya, berbagai masalah dalam desain mekanisme (misalnya dalam lelang kombinatorial), dll. Apakah algoritma aproksimasi semacam itu berguna di bagian lain dari teori di masa lalu atau mereka belajar murni untuk kepentingan mereka sendiri?

Catatan: Saya tidak bertanya tentang aplikasi praktis karena sejauh yang saya tahu, di dunia nyata, kebanyakan heuristik yang diterapkan daripada algoritma aproksimasi dan heuristik jarang diinformasikan oleh wawasan yang diperoleh dengan mempelajari algoritma aproksimasi untuk masalah.

Saya sangat tidak setuju dengan paragraf terakhir. Pernyataan selimut seperti itu tidak berguna. Jika Anda melihat makalah di banyak area sistem seperti jaringan, basis data, AI dan sebagainya, Anda akan melihat bahwa banyak algoritma perkiraan digunakan dalam praktiknya. Ada beberapa masalah di mana seseorang menginginkan jawaban yang sangat akurat; misalnya mengatakan sebuah maskapai penerbangan yang menarik dalam mengoptimalkan penjadwalan armadanya. Dalam kasus seperti itu orang menggunakan berbagai heuristik yang membutuhkan waktu komputasi yang substansial tetapi mendapatkan hasil yang lebih baik daripada yang dapat diberikan oleh algoritma perkiraan umum.

Sekarang untuk beberapa alasan teoritis untuk mempelajari algoritma aproksimasi. Pertama, apa yang menjelaskan fakta bahwa ransel sangat mudah dalam prakteknya sementara pewarnaan grafik cukup sulit? Keduanya NP-Hard dan waktu-dapat direduksi satu sama lain. Kedua, dengan mempelajari algoritma aproksimasi untuk kasus-kasus khusus dari suatu masalah, seseorang dapat menunjukkan dengan tepat kelas instance mana yang mungkin mudah atau sulit. Sebagai contoh kita tahu bahwa banyak masalah mengakui PTAS dalam grafik planar dan minor-gratis sementara mereka jauh lebih sulit dalam grafik umum yang sewenang-wenang. Ide aproksimasi meliputi desain algoritma modern. Sebagai contoh, orang menggunakan algoritma streaming data dan tanpa lensa aproksimasi sulit untuk memahami / merancang algoritma karena bahkan masalah sederhana tidak dapat diselesaikan dengan tepat.

$S_2^p \subseteq ZPP^{NP}$

Saya juga tidak setuju dengan "catatan", setidaknya dinyatakan dalam generalitas ini. Terkait dengan hal ini, apakah ada yang tahu jika ceramah penghargaan Kanellakis David Johnson tersedia di suatu tempat?

Juga, setelah kami menyadari bahwa semua masalah NP-hard setara dengan kompleksitas terburuk dari solusi yang tepat, itu sangat wajar untuk menanyakan tentang kompleksitas menemukan solusi perkiraan. Dan Chandra membuat poin bagus tentang perubahan perspektif yang membawa algoritma perkiraan untuk desain algoritma.

$O(\log n)$

Heuristik terbaik benar-benar algoritma perkiraan. Algoritma pendekatan yang paling indah hanyalah heuristik "bodoh" yang berfungsi. Misalnya, pencarian lokal untuk clustering, greedy clustering (Gonzalez), satu untuk harga dua, berbagai algoritma serakah, dll, dll, dll.

Jadi mempelajari algoritma aproksimasi sebenarnya tentang memahami heuristik yang dijamin sebagai algoritma aproksimasi. Harapannya adalah bahwa penelitian tentang algoritma aproksimasi menciptakan dua jenis pemupukan silang:

• Pindahkan ide yang berfungsi dari heuristik ke dalam alat desain algoritma. Demikian pula, pindahkan ide dari desain algoritma ke heuristik / algoritma yang bekerja dengan baik dalam praktik.
• fertilisasi silang antara seseorang yang baru saja lulus dan suatu posisi.

Singkatnya, dunia tidak tepat, input tidak tepat, fungsi target dioptimalkan oleh berbagai masalah algoritma tidak tepat dan paling tidak mewakili perkiraan fuzzy untuk apa yang diinginkan, dan perhitungan tidak tepat. Mengapa ada orang yang mempelajari algoritma yang tepat? (Jawab: Karena algoritma yang tepat adalah algoritma perkiraan yang sangat bagus.)

Di dunia nyata, ada sangat sedikit algoritme yang tepat - Anda harus menggunakan aproksimasi agar relevan dari jarak jauh ...

Berurusan dengan masalah dengan variabel kontinu sangat mengganggu dengan algoritma yang tepat. Misalnya, apa artinya menentukan bobot tepi dari instance TSP dengan bilangan real yang tepat?

Saat kami mengizinkan algoritma FPTAS untuk masalah ini, kami dapat mengukur parameter ini menjadi bilangan bulat. Ini membuat masalah jauh lebih baik (dapat menggunakan mesin Turing standar), tetapi menimbulkan kesalahan kecil.