Keberadaan

Pertimbangkan masalah Set yang Mendominasi dalam grafik umum, dan biarkan menjadi jumlah simpul dalam grafik. Algoritma pendekatan serakah memberikan jaminan perkiraan faktor 1 + log n , yaitu mungkin untuk menemukan dalam waktu polinomial solusi S sedemikian rupa sehingga | S | ≤ ( 1 + log n ) o p t , di mana o p t adalah ukuran set dominasi minimum. Ada batas yang menunjukkan bahwa kita tidak dapat meningkatkan ketergantungan pada log dan banyak$n$$1 + \log n$$S$$|S| \leq (1 + \log n) opt$$opt$$\log n$http://www.cs.duke.edu/courses/spring07/cps296.2/papers/p634-feige.pdf .

Pertanyaan saya: apakah ada algoritma pendekatan yang memiliki jaminan dalam hal bukannya n ? Dalam grafik di mana n sangat besar sehubungan dengan optimal, sebuah factor log n pendekatan akan jauh lebih buruk daripada faktor log o p t pendekatan. Apakah sesuatu seperti itu diketahui, atau adakah alasan mengapa ini tidak ada? Saya senang dengan algoritma waktu polinomial yang menghasilkan solusi S sedemikian rupa sehingga | S | ∈ O ( o p t c ) untuk beberapa konstanta $opt$$n$$n$$\log n$$\log opt$$S$$|S| \in O(opt^c)$$c$.

Saya pikir itu masih terbuka jika Dominating Set atau Hitting Set memiliki aproksimasi (OPT) untuk beberapa fungsi (nontrivial) f. Ini harus menjadi pertanyaan yang sangat sulit (dan mungkin dalam) untuk dijawab. Saya menganggapnya sebagai pertanyaan paling menarik dalam perkiraan parameter (bersama dengan pertanyaan analog untuk Clique). Anda mungkin ingin melihat survei saya [1] yang membahas hal ini. Perhatikan bahwa ditunjukkan dalam makalah yang lebih baru [2] bahwa "kepuasan sirkuit monoton untuk sirkuit weft-2", masalah yang lebih umum daripada Dominating Set, tidak memiliki pendekatan f (OPT) untuk f.

[1] D. Marx. Kompleksitas parameterisasi dan algoritme aproksimasi. The Computer Journal, 51 (1): 60-78, 2008.

[2] D. Marx. Masalah parameterisasi monoton dan antimonoton yang sama sekali tidak dapat diperkirakan. Dalam Prosiding Konferensi IEEE Tahunan ke-25 tentang Kompleksitas Komputasi, Cambridge, Massachusetts, 181-187, 2010.

Ini harus menjadi komentar, karena tidak langsung menjawab pertanyaan Anda, tetapi pertanyaan terkait. Mungkin trik serupa dari [1] akan memberi Anda jawaban.

Dalam [1] yang berikut ini terbukti:

$G=(V,E)$$k$$k$$G$$g(k)$$g(k)$$k$$G$$k$

$g(k)$

[1] Rodney G. Downey, Michael R. Fellows, Catherine McCartin dan Frances Rosamond. "Pendekatan Parameter dari Mendominasi Masalah Set". Pemrosesan Informasi Surat, Volume 109 Edisi 1, Desember, 2008.