Hubungan antara parameter tetap dan algoritma aproksimasi

13

Parameter dan pendekatan tetap adalah pendekatan yang sama sekali berbeda untuk menyelesaikan masalah yang sulit. Mereka memiliki motivasi yang berbeda. Perkiraan mencari hasil yang lebih cepat dengan solusi perkiraan. Parameter tetap mencari solusi yang tepat dengan kompleksitas waktu dalam hal eksponensial atau beberapa fungsi k dan fungsi polinomial dari n di mana n adalah ukuran input dan k adalah parameter. Contoh 2kn3 .

Sekarang pertanyaan saya, apakah ada hasil batas atas atau bawah berdasarkan hubungan antara parameter tetap dan pendekatan pendekatan atau mereka benar-benar tidak memiliki hubungan apa pun. Misalnya untuk masalah P dikatakan W[i] sulit untuk beberapa i>0 tidak ada hubungannya dengan memiliki algoritma c-aproksimasi atau PTAS. tolong berikan beberapa referensi

Prabu
sumber
1
Terkait, mungkin duplikat ?: Cstheory.stackexchange.com/questions/4906/…
Suresh Venkat
1
@suresh venkat Pertanyaan itu adalah tentang perbedaan dalam memahami parameter NP-complete dan fixed. ketika kita berbicara dalam hal kekerasan NP saja, maka set independen dan penutup vertex secara harfiah sama, tetapi ketika kita berbicara dalam hal parameter tetap mereka memiliki perbedaan besar. vertex cover memiliki fpt yang baik sedangkan set independen adalah W [1] keras
Prabu
tapi di sini saya mencari hubungan antara aproksimasi dan parameter tetap.
Prabu
Saya pikir tidak ada hubungan nyata di antara mereka, tetapi dengan menggunakan parameter tetap kita mungkin memiliki perkiraan yang baik, misalnya dalam kemasan bin (penjadwalan makespan) Anda dapat melihat hubungan ini, atau misalnya dalam grafik Treewidth yang dibatasi, kami memiliki perkiraan pada beberapa masalah .
Saeed

Jawaban:

16

Ada beberapa koneksi antara kompleksitas parameter dan algoritma aproksimasi.

Pertama, pertimbangkan parameterisasi standar yang disebut masalah. Di sini, parameter adalah apa yang akan Anda optimalkan dalam versi optimisasi masalah (ukuran penutup simpul untuk masalah Penutup Vertex, lebar penguraian pohon untuk masalah Treewidth, dll.). Mari kita secara konkret melihat Vertex Cover. Setiap kernel dengan jumlah linear dari simpul untuk Vertex Cover menyiratkan faktor konstan algoritma pendekatan polinomial-waktu: ke dalam solusi perkiraan, masukkan semua simpul yang telah dipaksa ke dalam solusi oleh algoritma kernelisasi, dan semua simpul dari contoh kernel . Di sisi lain, batas bawah pada faktor aproksimasi menyiratkan batas bawah pada ukuran kernel. Misalnya, di bawah Konjektur Game Unik, Khot dan Regev (JCSS 2008)mengesampingkan algoritma pendekatan untuk Vertex Tutup dengan rasio setiap , yang aturan dari sebuah kernel untuk Vertex Tutup dengan paling c k simpul, c < 2 , juga.c<2ckc<2

EDIT: Argumentasi untuk batas bawah kernel pada paragraf sebelumnya sangat informal, dan sejauh pengetahuan saya, terbuka apakah batas bawah pada ukuran kernel dapat dibuktikan, bahkan untuk Penutup Vertex. Seperti @Falk tunjukkan dalam komentar, argumen berlaku untuk sebagian besar (semua?) Kernel yang dikenal. Namun, saya tidak melihat bagaimana orang bisa mengecualikan keberadaan algoritma kernelisasi di mana solusi yang layak dari contoh kernel memiliki rasio perkiraan yang berbeda dari solusi yang sesuai dalam contoh awal.

Lalu, ada masalah PTAS versus FPTAS. Jika kita ingin menemukan solusi dalam dari optimal, kita dapat membuat parameter dengan 1 / ϵ . Kemudian, PTAS sesuai dengan algoritma XP dalam pengaturan parameter, sedangkan FPTAS sesuai dengan algoritma FPT. Untuk perkiraan batas bawah, kita mungkin tidak mengharapkan EPTAS untuk masalah yang parameterisasi standarnya adalah W [1] -hard: menjalankan EPTAS dengan ϵ = 1 / ( k + 1 ) akan menyelesaikan masalah tepat pada waktu FPT.(1+ϵ)1/ϵϵ=1/(k+1)

Akhirnya, algoritma aproksimasi FPT adalah sebuah algoritma dengan FPT running time dan rasio aproksimasi yang mungkin tergantung pada parameter. Sebagai contoh, parameterisasi standar masalah Cliquewidth memiliki algoritma aproksimasi FPT dengan rasio aproksimasi (Oum, WG 2005) , sedangkan parameterisasi standar Independent Dominating Set tidak memiliki algoritma aproksimasi FPT dengan rasio kinerja g ( k ) untuk setiap fungsi yang dapat dihitung g , kecuali FPT = W [2] (Downey et al., IWPEC 2006) . Lihat (Marx, The Computer Journal 2008)(23k+21)/k g(k)g untuk survei tentang perkiraan FPT.

Serge Gaspers
sumber
@Gasper Bisakah Anda melihat pertanyaan "Menemukan sub-turnamen asiklik maksimum yang diberikan dua sub-turnamen asiklik". Saya masih ragu dengan jawaban saya. Karena Anda telah bekerja dengan masalah terkait, Anda dapat membantu saya
Prabu
APAKAH paragraf pertama jawaban Serge benar? Apakah batas bawah pada aproksimasi menghasilkan batas bawah pada ukuran kernel? Pernyataan serupa ada di buku Niedermeier tetapi apakah pernyataan ini benar?
XXYYXX
1
@XXYYXX: Dalam jawaban Serge, ia menulis "Setiap kernel dengan jumlah linear dari simpul untuk Vertex Cover menyiratkan faktor konstan algoritma pendekatan polinomial-waktu" dengan bukti singkat. Lebih tepatnya, argumennya menunjukkan jika ada kernel dengan simpul ck untuk beberapa konstanta c, maka ada algoritma aproksimasi faktor-c. Kontrapositifnya adalah: jika tidak ada algoritma pendekatan faktor-c, maka tidak ada kernel dengan simpul ck.
Yoshio Okamoto
@ Prabu: Saya mengomentari jawaban Anda untuk pertanyaan lain. @Yoshio: Terima kasih telah menjawab pertanyaan @ XXYYXX.
Serge Gaspers
1
Bahkan mungkin untuk semua kernelisasi yang dikenal, argumen ini berlaku. Namun, saya tidak melihat alasan mengapa seharusnya tidak ada satu yang misalnya mengurangi ke masalah lain, kernel di sana, dan kemudian mengurangi kembali ke Vertex Cover, sehingga turunan yang dihasilkan tidak memiliki korespondensi simpul dengan yang awal. Jadi menurut saya satu-satunya hal yang benar-benar dapat kita tunjukkan adalah bahwa kernel yang subgraph mungkin tidak akan lebih kecil dari 2k.
Falk Hüffner
7

Ada teorema yang diketahui [1, Teorema 3.1], yang mencirikan kelas pendekatan melalui kelas parameter P F P T T :FPTASPFPT

Q=(IQ,SQ,fQ,optQ)NPQFPTASQPFPT

PFPT

NPQPFPTO(|x|O(1)kO(1))|x|x

Karakterisasi lain untuk dua kelas aproksimasi diusulkan dalam [2, Teorema 6.5].

Masalahnya adalah

  • PTASptasXPw

  • FPTASfptasPFPTw

(f)ptas(XP)PFPTw1ϵ

  1. Skema perkiraan waktu polinomial dan kompleksitas parameter . J. Chen et al. / Matematika Terapan Diskrit 155 (2007) 180 - 193.
  2. Struktur Perkiraan Polinomial-Waktu . EJ van Leeuwen et al. Laporan Teknis UU-CS-2009-034, Desember 2009.
Oleksandr Bondarenko
sumber