Saya tertarik pada kompleksitas parameter dari apa yang saya sebut masalah Set-h Memukul d-dimensi: diberi ruang rentang (yaitu sistem set / hypergraph) S = (X, R) memiliki dimensi-VC paling banyak d dan bilangan bulat positif k, apakah X berisi subset ukuran k yang mengenai setiap rentang dalam R?...
Pertimbangkan masalah set penutup minimum dengan batasan berikut: setiap set berisi paling banyak elemen kkk dan setiap elemen alam semesta terjadi di paling banyak set fff . Contoh: case k=4k=4k = 4 dan f=2f=2f = 2 setara dengan masalah penutup simpul minimum dalam grafik dengan derajat maksimum...
Apakah mungkin untuk menguji secara algoritmik apakah bilangan yang dihitung rasional atau bilangan bulat? Dengan kata lain, apakah mungkin bagi perpustakaan yang mengimplementasikan angka yang dapat dihitung untuk menyediakan fungsi isIntegeratau isRational? Saya menduga itu tidak mungkin, dan...
Diberikan seperangkat S dari matriks permutasi nxn (yang hanya sebagian kecil dari matriks permutasi n! Mungkin), bagaimana kita dapat menemukan subset ukuran-kecil T dari S sedemikian sehingga menambahkan matriks T memiliki setidaknya 1 di setiap posisi? Saya tertarik dengan masalah ini di mana S...
Apa variasi berikut pada penutup yang dikenal sebagai? Diberikan himpunan S, kumpulan C himpunan bagian dari S dan bilangan bulat positif K, apakah ada set K di C sehingga setiap pasangan elemen S terletak di salah satu himpunan bagian yang dipilih. Catatan: Tidak sulit untuk melihat bahwa...
Pertimbangkan kumpulan set F = { F 1 , F 2 , ... , F n } diF={F1,F2,…,Fn}F=\{F_1,F_2,\dotsc,F_n\} atas set dasar U = { e 1 , e 2 , ... , e n } diU={e1,e2,…,en}U=\{e_1,e_2,\dotsc,e_n\} mana | F i | |Fi||F_i| ≪ ≪\ll nnn dan e i ∈ F iei∈Fie_i \in F_i , dan biarkan kkk menjadi bilangan bulat...
Input adalah alam semesta UUU dan keluarga himpunan bagian dari UUU , mengatakan, F⊆2UF⊆2U{\cal F} \subseteq 2^U . Kami berasumsi bahwa subset di FF{\cal F} dapat menutupi UUU , yaitu, ⋃E∈FE=U⋃E∈FE=U\bigcup_{E\in {\cal F}}E=U . Sebuah urutan meliputi tambahan adalah urutan himpunan bagian di...
Jadi, masalah cover set sepele jika tidak ada set kandidat berpotongan satu sama lain. Namun, bagaimana jika ukuran persimpangan untuk setiap pasangan calon paling banyak 1? Apakah ini masalah NP-hard? Saya sangat menghargai wawasan apa pun. Terima kasih,
Banyak di sini mungkin menyadari batas bawah super-linear baru-baru ini Alon untuk ϵϵ\epsilon jaring dalam pengaturan geometris alami [PDF] . Saya ingin tahu apa, jika ada, seperti batas bawah yang menyiratkan tentang perkiraan masalah Set Cover / Hitting Set yang terkait. Untuk sedikit lebih...
Misalkan saya memiliki poligon sederhana dan bilangan bulat k . Apa saja pendekatan yang ada untuk menemukan jari-jari terkecil r sehingga saya bisa menutup S dengan k lingkaran jari-jari r ? Bagaimana jika r diperbaiki, dan saya ingin meminimalkan k
Seberapa sulit masalah Set Cover jika jumlah elemen dibatasi oleh beberapa fungsi (misalnya, lognlogn\log n ) di mana nnn adalah ukuran instance masalah. Secara formal, Misalkan U={e1,⋯,em}U={e1,⋯,em}\mathcal{U}=\{e_1, \cdots, e_m\} dan F={S1,⋯,Sn}F={S1,⋯,Sn}\mathcal{F} = \{S_1, \cdots, S_n\}...
Saya mencoba menunjukkan bahwa masalah tertentu tidak dapat diperkirakan dengan pengurangan dari set penutup. Reduksi saya mengubah sebuah instance dengan ground set ukuran dan menjadi instance dari masalah saya di mana parameter tertentu berukuran . Saya kemudian dapat menunjukkan bahwa contoh set...
Apakah masalah berikut NP-hard? Diberikan satu set bilangan real (target) x 1 , … , x N dan "trisula" yang didefinisikan oleh dua jarak a , b dari pusat trisula, berapakah angka minimum K dari posisi p 1 , ... , p K dari trisula untuk mencakup semua target, yaitu K ⋃ k = 1 { p k - a , p k , p k +...