Mengapa rasio aproksimasi diferensial tidak dipelajari dengan baik dibandingkan dengan yang standar meskipun manfaatnya diklaim?

$\sup\frac{A}{OPT}$ $MIN$ $A$ $A$ $OPT$ $\inf\frac{\Omega-A}{\Omega-OPT}$ $\Omega$

itu memberikan rasio perkiraan yang sama untuk masalah seperti penutup simpul minimum dan set independen maksimum yang diketahui hanya realisasi berbeda dari masalah yang sama;
ini memberikan rasio yang sama untuk versi max dan min dari masalah yang sama. Pada saat yang sama kita tahu dalam teori standar MIN TSP dan MAX TSP memiliki rasio yang sangat berbeda.
Ini mengukur jarak tidak hanya ke optimal tetapi juga ke pessimum . Jadi dalam kasus teori pendekatan standar Vertex Cover mengatakan bahwa adalah batas atas terbaik. Tapi essentialy adalah rasio maksimum antara pessimum dan optimal. Dengan demikian algoritma tersebut dijamin untuk menghasilkan solusi dengan nilai terburuk. $\Omega$ $2$ $2$

Pro argumen saya adalah: dalam analisis asimptotik kami tidak mempertimbangkan konstanta pertimbangan dan persyaratan tingkat rendah (di sini saya mengingat kutipan oleh Avi Widgerson: "Kami berhasil karena kami menggunakan tingkat abstraksi yang tepat.") Dan ini adalah tingkat abstraksi untuk membandingkan penggunaan sumber daya algoritma. Tetapi ketika kita mempelajari perkiraan kita dengan beberapa alasan memperkenalkan perbedaan di tempat-tempat di mana kita dapat menghindarinya.

Pertanyaanku adalah

mengapa teori aproksimasi diferensial sangat kurang dipelajari. Atau argumen yang terlibat tidak cukup kuat?

ds.algorithms approximation-algorithms approximation-hardness Oleksandr Bondarenko
sumber

Saya belum pernah melihat gagasan ini sebelumnya dan berpikir itu setidaknya menarik. Sangat ingin tahu jawabannya! (walaupun alasan sebenarnya bisa sepele seperti "Doh, tidak pernah memikirkan hal itu" atau "Bukti semakin sulit" atau "Tidak dapat membandingkannya dengan hasil lain ketika saya mulai")

Raphael

Jawaban:

Ada dua interpretasi dari klaim "algoritma menemukan -approximation of problem " $A$ $\alpha$ $P$ :

Soal adalah mudah untuk memecahkan cukup baik, karena kita memiliki algoritma yang menemukan pendekatan yang baik. $P$
Algoritma adalah baik , karena ia menemukan pendekatan yang baik. $A$

Saya pikir definisi klasik dari faktor aproksimasi menekankan interpretasi pertama. Kami mengklasifikasikan masalah berdasarkan seberapa mudah mereka menyelesaikannya dengan cukup baik.

Rasio aproksimasi diferensial tampaknya memberikan bobot lebih pada interpretasi kedua: kami tidak ingin "menghargai" algoritma sepele (misalnya, algoritma yang hanya menghasilkan set kosong, atau set semua node).

Tentu saja, keduanya adalah sudut pandang yang valid, tetapi keduanya adalah sudut pandang yang berbeda .

Kami juga dapat mempelajari pertanyaan dari perspektif yang sedikit lebih praktis. Sayangnya, vertex mencakup karena itu tidak memiliki banyak kegunaan langsung, tetapi demi argumen, mari kita pertimbangkan dua aplikasi ini (agak dibuat-buat):

Vertex cover: node adalah komputer dan edge adalah tautan komunikasi; kami ingin memantau semua tautan komunikasi dan karenanya setidaknya satu titik akhir dari setiap sisi harus menjalankan proses khusus.
Set independen: node adalah pekerja dan memodelkan konflik di antara aktivitas mereka; kami ingin menemukan serangkaian kegiatan bebas konflik yang dapat dilakukan secara bersamaan.

Sekarang kedua masalah memiliki solusi sepele: himpunan semua node adalah penutup simpul, dan himpunan kosong adalah himpunan independen.

Perbedaan utama adalah bahwa dengan masalah vertex cover, solusi sepele menyelesaikan pekerjaan . Tentu, kami menggunakan lebih banyak sumber daya daripada yang diperlukan, tetapi setidaknya kami memiliki solusi yang dapat kami gunakan dalam praktik. Namun, dengan masalah set independen, solusi sepele benar - benar tidak berguna . Kami tidak membuat kemajuan sama sekali. Tidak ada yang melakukan apa pun. Tugas tidak pernah selesai.

Demikian pula, kita dapat membandingkan solusi hampir-sepele: vertex penutup yang terdiri dari titik akhir dari pencocokan maksimal, dan mandiri set yang adalah komplemen dari . Sekali lagi, tentu menyelesaikan pekerjaan dalam aplikasi kita, dan kali ini kita tidak menyia-nyiakan sumber daya lebih dari faktor dua. Namun, mungkin lagi set kosong, yang sama sekali tidak berguna. $C$ $I$ $C$ $C$ $I$

Oleh karena itu definisi standar dari jaminan pendekatan secara langsung memberi tahu kita apakah solusi tersebut bermanfaat atau tidak. 2-pendekatan penutup vertex menyelesaikan pekerjaan. Perangkat independen tanpa jaminan perkiraan mungkin sama sekali tidak berguna.

Dalam arti tertentu, rasio perkiraan diferensial mencoba mengukur "seberapa tidak sepele" solusinya, tetapi apakah itu penting dalam salah satu dari aplikasi ini? (Apakah itu penting dalam aplikasi apa pun?)

Jukka Suomela
sumber

Saya tidak mengerti maksud Anda di bagian kedua. Setiap pilihan yang terlalu tinggi dari simpul adalah penutup simpul yang layak, kita tidak perlu tahu bahwa algoritma adalah perkiraan 2 untuk itu. Di sisi lain, bahkan perkiraan 2 untuk set independen mungkin sangat menghasilkan solusi yang tidak layak. Jadi tampak bahwa bahaya ketidakterbatasan terkait dengan masalah, bukan pada batas perkiraan yang tidak diketahui.

Raphael

@ Raphael: Perkiraan 2 set independen maksimum adalah, menurut definisi, set independen (dan cukup besar; tentu saja bukan set kosong).

Jukka Suomela

Sudahlah, baca terlalu cepat. Tapi tetap saja, saya pikir poin Anda harus diutarakan seperti: Algoritma tanpa jaminan perkiraan menyelesaikan pekerjaan dalam kasus VC, tetapi tidak dalam IS. (Anda membandingkan apel dan pir di sana, bukan?) Namun, bagaimana penelitian ini terkait dengan pilihan jaminan? Entah akan lakukan untuk memilih solusi yang layak.

Raphael

@ Raphael: Tidak, saya mengatakan bahwa VC sepele memiliki jaminan pendekatan yang terbatas (sesuatu seperti

), dan menyelesaikan pekerjaan, sedangkan IS yang sepele tidak memiliki jaminan pendekatan yang terbatas, dan tidak mendapatkan pekerjaan selesai. Oleh karena itu jaminan perkiraan memberi tahu setidaknya sesuatu tentang seberapa berguna solusinya.

O (Δ)

$O(\Delta)$

Jukka Suomela

Memberi +1 karena contohnya menyenangkan. Saya tidak berpikir bahwa ada perbedaan yang jelas antara "masalahnya mudah" dan "ada algoritma yang baik," tapi saya agak memahaminya pada tingkat yang tidak jelas.

Tsuyoshi Ito

Saya tidak terbiasa dengan gagasan tentang pendekatan diferensial, dan saya tidak punya teori mengapa itu tidak dipelajari dengan baik. Namun, saya ingin menunjukkan bahwa tidak selalu diinginkan untuk menggambarkan kinerja suatu algoritma aproksimasi dengan ukuran tunggal. Dalam hal ini, saya merasa sulit untuk menyetujui bahwa beberapa ukuran lebih baik daripada yang lain.

Misalnya, seperti yang Anda nyatakan, penutup simpul minimum mengakui algoritma pendekatan waktu 2 polinomial sedangkan NP-sulit untuk memperkirakan set independen maksimum untuk setiap rasio konstan. Meskipun saya mengerti bahwa ini bisa mengejutkan pada pandangan pertama, itu memiliki makna yang sah: (1) tutupan simpul minimum dapat didekati dengan baik ketika kecil tetapi (2) tidak dapat didekati dengan baik ketika besar. Ketika kami menyatakan bahwa NP-hard untuk mendekati penutup vertex minimum (dan set independen maksimum) dengan rasio aproksimasi diferensial konstan positif, kami secara efektif mengabaikan properti (1). Mungkin cukup baik untuk beberapa tujuan mengabaikan properti (1), tetapi tentu saja tidak selalu demikian.

Perhatikan bahwa kami tidak selalu menggunakan rasio aproksimasi untuk menggambarkan kinerja algoritma aproksimasi. Sebagai contoh, untuk menyatakan hasil yang tidak dapat diperkirakan berdasarkan teorema PCP secara umum, kita memerlukan formulasi berdasarkan masalah kesenjangan. Lihat jawaban saya untuk pertanyaan lain untuk perincian. Dalam hal ini, tidak menggunakan rasio perkiraan standar atau menggunakan rasio perkiraan diferensial memungkinkan kita untuk menyatakan hasilnya secara umum penuh.

Tsuyoshi Ito
sumber

0

$0$

2

$2$

O P T ⩾ n / 2

$OPT\geqslant n/2$

@Oleksandr: “Dalam hal Vertex Cover meskipun aproksimasi bertepatan dengan solusi terburuk ketika OPT⩾n / 2 kita memiliki rasio 2.” Apakah Anda menganggapnya sebagai kerugian atau tidak, adalah sudut pandang. Orang mungkin berpendapat bahwa jika setiap solusi memiliki nilai objektif dalam faktor 2, maka tidak masalah apa solusi yang dihasilkan algoritma. Rasio perkiraan standar memodelkan situasi seperti ini.

Tsuyoshi Ito

Jika faktor 2 atau faktor kecil lainnya adalah solusi terburuk maka hasil seperti itu tidak banyak berguna.

Oleksandr Bondarenko

@Olexandr: Seperti yang saya katakan, itu adalah sudut pandang.

Tsuyoshi Ito

Seperti yang ditunjukkan Tsuyoshi, masalahnya mungkin untuk jenis argumen apa yang ingin Anda gunakan untuk mendapatkan ikatan. Berikut ini, saya akan mencoba mengembangkan dua motivasi yang berbeda.

$\alpha = \frac{A}{OPT}$

$\alpha = \frac{\Omega - A}{\Omega - OPT}$ $\alpha\cdot 100\%$

Jadi, tergantung pada jenis pernyataan apa yang diturunkan dari ikatan yang diturunkan, Anda harus memilih alternatif yang tepat.

$[\Omega, OPT]$

Raphael
sumber