Apa varian dari masalah penutup yang dikenal sebagai?

Input adalah alam semesta $U$ dan keluarga himpunan bagian dari $U$ , mengatakan, ${\cal F} \subseteq 2^U$ . Kami berasumsi bahwa subset di ${\cal F}$ dapat menutupi $U$ , yaitu, $\bigcup_{E\in {\cal F}}E=U$ .

Sebuah urutan meliputi tambahan adalah urutan himpunan bagian di ${\cal F}$ , katakanlah, ${\cal A}=\{E_1,E_2,\ldots,E_{|{\cal A}|}\}$ , itu memuaskan

1) $\forall E\in {\cal A}, E\in {\cal F}$ ,

$\forall i>1$ $\bigcup_{j=1}^{i-1}E_i \subsetneq \bigcup_{j=1}^{i}E_i$

Masalahnya adalah untuk menemukan urutan penutup tambahan dari panjang maksimum (yaitu, dengan maksimum ). Perhatikan bahwa urutan panjang maksimum akhirnya harus menutupi , yaitu, . $|{\cal A}|$ $U$ $\bigcup_{E\in {\cal A}}E=U$

Saya telah berusaha untuk menemukan suatu algoritma atau algoritma perkiraan untuk menemukan urutan penutup inkremental terpanjang. Saya hanya ingin tahu apa yang disebut varian masalah cover set ini. Terima kasih!

cc.complexity-theory ds.algorithms approximation-algorithms optimization set-cover Kohorologi Cech
sumber

Anda memerlukan keluarga himpunan bagian untuk menutupi alam semesta ? Karena dengan begitu tentu saja Anda dapat mengatur masalah cover yang lebih sulit karena Anda mencari set cover dengan properti tambahan. Dengan kata lain, set cover dikurangi untuk masalah Anda. Pada wiki set penutup juga merupakan hasil innapproximability untuk set penutup.

A

$\cal{A}$

U

$\cal{U}$

Harry

Hanya sebuah pengamatan (terlalu kecil untuk dijawab): ketika himpunan bagian Anda berukuran dua maka apa yang Anda cari pada dasarnya adalah hutan yang membentang.

David Eppstein

Mungkin bukan hal baru bagi OP, tetapi di sini ada beberapa pengamatan. (1) Nilai optimal selalu paling banyak | U |. Apakah nilai optimal sama dengan | U | atau tidak dapat ditentukan secara efisien oleh algoritma serakah yang mencoba meminimalkan jumlah elemen yang dibahas. (2) Algoritma serakah yang sama juga berfungsi jika semua set dalam F berukuran dua, lihat komentar David Eppstein. (3) Algoritma serakah yang sama tidak bekerja secara umum (mendesah). Contoh tandingan: F = {{1,2,3}, {1,4,5,6}, {2,4,5,6}, {3,4,5,6}}.

Tsuyoshi Ito

Masalahnya tidak benar-benar terlihat seperti masalah set penutup sama sekali ... Lebih seperti hibrida antara pencocokan dan pencocokan terinduksi dalam grafik bipartit. Reformulasi setara yang bagus adalah bahwa sebuah keluarga buruk jika tidak ada elemen yang tercakup tepat oleh satu set dalam keluarga. Masalahnya adalah untuk menemukan subfamili dari sehingga tidak memiliki subfamili buruk.

A

${\cal A}$

F

${\cal F}$

A

${\cal A}$

daniello

@Neal Young tidak buruk karena dicakup oleh tepat satu set (yaitu ).

F

${\cal F}$

b

$b$

{a, b}

$\{a,b\}$

daniello

Jawaban:

Di sini saya menunjukkan bahwa masalahnya adalah NP-complete.

Kami mengonversi CNF ke instance masalah Anda sebagai berikut. Misalkan variabel CNF adalah dan klausa adalah , di mana . Misalkan mana semua set dalam gabungan sepenuhnya terpisah. Faktanya, dan , sedangkan adalah kumpulan kardinalitas . Juga tunjukkan dan perbaiki untuk setiap keluarga yang bertambah panjang di dalamnya, dilambangkan dengan untuk $n$ $x_i$ $m$ $C_j$ $n<m$ $U=\cup_i (A_i\cup B_i\cup Z_i)$ $A_i=\{a_{i,j}\mid x_i\in C_j\}\cup\{a_{i,0}\}$ $B_i=\{b_{i,j}\mid x_i\in C_j\}\cup\{b_{i,0}\}$ $Z_i$ $k=2n+1$ $Z=\cup_i Z_i$ $Z_i$ $k$ $Z_{i,l}$ $l=1..k$ . Untuk setiap variabel , kami menambahkan set ke , setiap set formulir dan . Untuk setiap klausa , kami menambahkan satu set ke , yang berisi , dan untuk setiap elemen dan untuk setiap elemen . $x_i$ $2k$ $\mathcal F$ $A_i \cup Z_{i,l}$ $B_i \cup Z_{i,l}$ $C_j$ $\mathcal F$ $Z$ $x_i\in C_j$ $\{a_{i,j}\}$ $\bar x_i\in C_j$ $\{b_{i,j}\}$

Misalkan rumusnya memuaskan dan memperbaiki tugas yang memuaskan. Kemudian pilih set dari formulir atau , tergantung pada apakah benar atau tidak. Ini adalah set inkremental . Sekarang tambahkan set sesuai dengan klausa. Ini juga terus meningkatkan ukuran, karena klausa tersebut memuaskan. Akhirnya, kita bahkan dapat menambahkan set lebih (satu untuk setiap variabel) untuk membuat penutup urutan . $k$ $A_i \cup Z_{i,l}$ $B_i \cup Z_{i,l}$ $x_i$ $nk$ $m$ $k$ $U$

Sekarang anggaplah bahwa set diletakkan dalam urutan tambahan. Perhatikan bahwa paling banyak set yang sesuai dengan dapat dipilih untuk setiap . Jadi, jika tidak ada set klausa dalam urutan inkremental, paling banyak dapat dipilih, yang terlalu sedikit. Perhatikan bahwa segera setelah set klausa dipilih, kita dapat memilih paling banyak dua set yang sesuai dengan masing-masing , total paling banyak set . Oleh karena itu, kita harus memilih setidaknya set variabel sebelum set klausa diambil. Tetapi karena kita dapat memilih paling banyak untuk setiap , ini berarti bahwa untuk masing-masing kita telah memilih setidaknya $n(k+1)+m$ $k+1$ $x_i$ $x_i$ $n(k+1)$ $x_i$ $2n$ $n(k-1)$ $k+1$ $x_i$ $1$ , seperti . Ini menentukan "nilai" dari variabel, sehingga kita hanya dapat memilih klausa "benar". $k=2n+1$

Pembaruan: Mengubah nilai dari menjadi seperti yang ditunjukkan oleh Marzio. $k$ $n$ $2n+1$

domotorp
sumber

Klarifikasi: Saya dengan cepat memeriksa konstruksi untuk rumus yang tidak memuaskan ( ) tetapi tampaknya kita dapat membangun urutan dari meningkatkan set . Mungkin saya membuat kesalahan: apakah kita memiliki ?

x_{1} \land \neg x_{1}

$x_1 \land \neg x_1$

n = k = 1, m = 2

$n=k=1, m=2$

n (k + 1) + m = 4

$n(k+1)+m = 4$

F

$\mathcal F$

F = {{a_{1, 0}, a_{1, 1}, a_{1, 2}, z_{1}}, {b_{1, 0}, b_{1, 1}, b_{1, 2}, z_{1}}, {a_{1, 1}, z_{1}}, {b_{1, 2}, z_{1}}}

$\mathcal F= \{ \{ a_{1,0}, a_{1,1}, a_{1,2}, z_1 \}, \{ b_{1,0}, b_{1,1}, b_{1,2}, z_1\}, \{ a_{1,1}, z_1 \}, \{ b_{1,2}, z_1 \} \}$

Marzio De Biasi

Mengenal Anda dan saya sendiri, saya yakin kesalahannya adalah milik saya ... Saya pikir kita harus mendapatkan , tetapi tentu saja itu masih masalah. OK, saya melihat di mana saya membuat kesalahan, saya memperbaikinya sebentar lagi, terima kasih

F = {{a_{1, 0}, a_{1, 1}, z_{1}}, {b_{1, 0}, b_{1, 2}, z_{1}}, {a_{1, 1}, z_{1}}, {b_{1, 2}, z_{1}}}

${\mathcal F}=\{\{a_{1,0},a_{1,1},z_1\}, \{b_{1,0},b_{1,2},z_1\},\{a_{1,1},z_1\}, \{b_{1,2},z_1\}\}$

domotorp

Ok, saya akan melihatnya besok! Hanya sebuah catatan, dapatkah Anda menulis (dalam komentar) apa itu untuk dan apa "nilai target" untuk panjang urutan penutup (apakah k)? Karena, dalam jawaban yang dimodifikasi Anda menetapkan terlebih dahulu, kemudian berbicara tentang set dimasukkan ke dalam urutan tambahan ; apakah benar (saya belum mencoba reduksi)?

F

$\mathcal F$

x_{i} \land \neg x_{i}

$x_i \land \neg x_i$

k = 2 n + 1

$k = 2n+1$

n (k + 1) + m = 2 n^{2} + 2 n + m

$n(k+1)+m = 2n^2+2n + m$

Marzio De Biasi

F = {{a_{1, 0}, a_{1, 1}, z_{1},}, {a_{1, 0}, a_{1, 1}, z_{1}, z_{2}}, {a_{1, 0}, a_{1, 1}, z_{1}, z_{2}, z_{3}}, {b_{1, 0}, b_{1, 2}, z_{1}}, {b_{1, 0}, b_{1, 2}, z_{1}, z_{2}}, {b_{1, 0}, b_{1, 2}, z_{1}, z_{2}, z_{3}}, {a_{1, 1}, z_{1}, z_{2}, z_{3}}, {b_{1, 2}, z_{1}, z_{2}, z_{3}}}

${\mathcal F}=\{\{a_{1,0},a_{1,1},z_1,\},\{a_{1,0},a_{1,1},z_1,z_2\},\{a_{1,0},a_{1,1},z_1,z_2,z_3\},\{b_{1,0},b_{1,2},z_1\},\{b_{1,0},b_{1,2},z_1,z_2\},\{b_{1,0},b_{1,2},z_1,z_2,z_3\},\{a_{1,1},z_1,z_2,z_3\},\{b_{1,2},z_1,z_2,z_3\}\}$

domotorp

Saya pikir ini benar sebagai , tetapi kami hanya memiliki panjang urutan tambahan.

n (k + 1) + m = 6

$n(k+1)+m=6$

5

$5$

domotorp

Ini adalah masalah pengepakan di bawah batasan bahwa untuk solusi , untuk setiap subset , kami memiliki bahwa selalu ada elemen dalam , yang tercakup tepat sekali. $\mathcal{A}$ $\mathcal{B} \subseteq \mathcal{A}$ $\bigcup_{X \in \mathcal{B}} X$

Bukti: Diberikan solusi untuk masalah Anda, segera memiliki properti ini. Memang, jika adalah solusi optimal untuk masalah Anda, maka pertimbangkan subset dari set ini, dan anggap adalah set terakhir dalam urutan ini yang muncul dalam . Dengan properti yang diperlukan bahwa solusinya adalah inkremental, maka mencakup elemen yang tidak ada set sebelumnya meliputi, yang menyiratkan properti di atas. $E_1, \ldots, E_m$ $\mathcal{B}$ $E_i$ $\mathcal{B}$ $E_i$

Adapun arah lainnya, juga mudah. Mulai dari solusi , temukan elemen yang tercakup tepat sekali, atur sebagai set terakhir dalam urutan, hapus set ini, dan ulangi. QED. $\mathcal{A}$

Ini adalah masalah yang cukup alami ....

Pengingat cepat: Dalam masalah pengemasan set, diberikan sekumpulan set, temukan subset set maksimal, yang memenuhi beberapa kendala tambahan (misalnya, tidak ada elemen yang tercakup lebih dari 10 kali, dll).

Sariel Har-Peled
sumber

Apakah jawaban ini hanya membuktikan bahwa pertanyaan itu wajar, atau adakah hal lain yang juga Anda klaim?

domotorp

Ini menyatakannya dengan cara yang lebih sederhana. Tidak?

Sariel Har-Peled

Ya, saya setuju untuk itu.

domotorp