Bagaimana Anda bisa mengikat kesalahan perkiraan tanpa mengetahui solusi optimal?

14

Saya telah melihat situs ini dan mengatakan bahwa orang menemukan solusi untuk tur TSP yang hanya 0,031% lebih tinggi dari tur optimalnya. Tanpa menemukan tur yang optimal bagaimana mereka tahu berapa lama seharusnya?

complexity-theory approximation Ilya Gazman
sumber
4
Solusinya adalah AT PALING 0,031% lebih tinggi dari tur optimal. Tanpa menemukan tur yang optimal, orang masih dapat menemukan batas yang lebih rendah di atasnya dan pada algoritma aproksimasi, yang karenanya memungkinkan untuk "membandingkan" solusi perkiraan dengan solusi optimal.
Tpecatte
3
Anda harus benar-benar mengambil buku tentang teori kompleksitas dan / atau bagaimana menyelesaikan masalah NP-hard . Anda memiliki sedikit harapan untuk benar-benar menyelesaikan P? = NP dalam hidup Anda dan meyakinkan siapa pun yang Anda lakukan jika Anda terus mengeluarkan proposal / pertanyaan yang membuktikan bahwa Anda belum memahami konsep sarjana. Tentu saja, kami dapat membantu Anda memahami ini.
Raphael
akan sangat membantu jika Anda mengutip orang yang menyatakan batas itu [TO, same]. afaik, tidak ada batas waktu-P yang diketahui secara umum. ada batas aproksimasi lain yang dinyatakan dalam fungsi parameter masalah misalnya titik, dll.
vzn

Jawaban:

8

Secara umum ketika Anda ingin mengikat rasio aproksimasi dari suatu algoritma, Anda mencari batas bawah yang mudah pada nilai optimal. Yang paling mudah adalah relaksasi LP dari formulasi ILP (yang dipilih secara tepat) dari masalah. Kadang-kadang hal-hal lain digunakan, untuk TSP misalnya Anda juga dapat menggunakan berat MST (tur optimal minus satu tepi adalah pohon, sehingga tidak dapat menimbang kurang dari MST).

Untuk contoh tertentu Anda tentu saja masih bisa menggunakan hal yang Anda gunakan dalam bukti Anda, yaitu Anda dapat memecahkan LP dan membandingkan solusi heuristik Anda dengan nilai LP. Jika Anda memiliki lebih banyak waktu CPU di tangan, Anda juga dapat memulai proses cabang-dan-terikat untuk menyelesaikan ILP. Bahkan jika Anda tidak menyelesaikan ILP sepenuhnya, Anda mendapatkan batas bawah yang lebih baik dari dualitas LP.

adrianN
sumber
Bisakah Anda jelaskan atau beri saya tautan untuk membaca. Apa itu LP, ILP, MST
Ilya Gazman
1
Saya mengedit jawaban saya untuk memasukkan tautan wikipedia.
adrianN