Menemukan sampul minimal subset dari produk kartesius terbatas oleh produk kartesius

11

Diberikan subset dari produk kartesius dari dua set yang terbatas, saya ingin menemukan penutup minimal dengan set yang merupakan produk kartesius itu sendiri.I×J

Misalnya, mengingat produk antara dan , saya dapat mengamati subset dan coba untuk menutupinya dengan jumlah minimal produk kartesius.J = { 1 , 2 , 3 } { ( A , 2 ) , ( B , 3 ) , ( B , 2 ) }I={A,B,C}J={1,2,3}{(A,2),(B,3),(B,2)}

Dua cara untuk melakukannya adalah dan , keduanya membutuhkan 2 produk. Solusi yang kurang optimal mungkin memecahnya menjadi 3 produk sepele.{ A , B } × { 2 } + { B } × { 3 }{A}×{2}+B×{2,3}{A,B}×{2}+{B}×{3}

Dapatkah penutup optimal semacam itu ditemukan secara efisien (misalnya dalam waktu polinomial)?

algorithms set-cover yuvalm2
sumber
mengingatkan saya pada masalah ini, "factoring cartesian join of vektor bit" (cstheory.SE, diucapkan jauh berbeda) yang memiliki koneksi ke teori rangkaian batas bawah. konteks apa masalah Anda muncul?
vzn
Konteks saya adalah keamanan jaringan. Dalam jaringan besar dengan banyak server, kebijakan keamanan menentukan mana yang dapat digunakan untuk berbicara. Jika kebijakan semacam itu dibangun secara bertahap dalam jangka waktu yang lama, (seperti biasanya), uraian kebijakan keamanan dapat disederhanakan dengan menggabungkan aturan keamanan bersama. Saya ingin menemukan penyederhanaan yang optimal.
yuvalm2
Apakah hanya jumlah produk yang ingin diperkecil? Jika demikian, apa yang salah dengan menggunakan sebagai sampul Anda? Itu akan mencakup semua yang ada di subset Anda (dan beberapa lagi). Apakah Anda memiliki persyaratan bahwa solusinya tidak hanya mencakup subset, tetapi juga harus menghindari menutupi apa pun di luar subset? I×J
DW
1
Juga, karena ini berasal dari aplikasi praktis (dan jadi Anda mungkin mencari solusi praktis), dapatkah Anda memberikan gambaran ukuran parameter yang khas? misalnya, ukuran khas,, dan bagian Anda, hingga dalam urutan besarnya atau lebih; atau rentang nilai tipikal? Ini mungkin membantu mengevaluasi teknik mana yang paling efektif. Saya teringat peta minimalisasi logika , DNF , dan Karnaugh . | J ||I||J|
DW
3
Mungkin cara lain untuk merumuskan ini adalah sebagai berikut: Mengingat bipartit grafik menemukan sejumlah minimum geng bipartit (atau bi-klik-klik) yang mencakup . Setiap klik berhubungan dengan produk unik di ruang kartesian Anda. EG=(L,R,E)E
Nicholas Mancuso

Jawaban:

2

NM merumuskan kembali masalah ini dalam komentar sebagai menemukan jumlah minimum klik bipartit (bi-klik) yang mencakup grafik bipartit. dua set yang Anda sebutkan adalah 2 set simpul dari grafik bipartit. produk cartesian dari himpunan bagian dari dua set simpul adalah bikli. wikipedia menyatakan ini adalah masalah dimensi bipartit dan merupakan masalah GT18 di Garey dan Johnson , terbukti NP lengkap berdasarkan reformulasi langsung dari masalah dasar set SP7.

vzn
sumber