Atur Cover untuk Matriks Permutasi

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 adalah subkelompok kecil dari S_n. Saya bertanya-tanya apakah mungkin untuk menemukan (dan mengimplementasikan!) Algoritma perkiraan yang jauh lebih cepat daripada algoritma serakah (jalankan berkali-kali sampai mendapat 'beruntung', yang merupakan prosedur yang sangat lambat tetapi meskipun demikian telah memberikan beberapa batas optimal dekat) dalam kasus-kasus kecil), atau apakah jaminan ketidak-taksiran menjamin bahwa saya tidak bisa.

Beberapa fakta mudah tentang masalah ini: Panjang dan sekelompok matrik permutasi matrik memecahkan masalah ini, tentu saja secara optimal. (Setidaknya n matriks diperlukan karena setiap matriks permutasi memiliki n satu dan ada n ^ 2 yang diperlukan.)

Set S yang saya tertarik tidak memiliki grup n-siklik di dalamnya.

Masalah ini adalah kasus penutup set yang sangat spesial. Memang, jika kita membiarkan X menjadi himpunan (1,2, ... n) * (1,2, ... n), dengan elemen n ^ 2, maka setiap matriks permutasi sesuai dengan ukuran n subset, dan saya Sedang mencari subkoleksi terkecil dari himpunan bagian ini yang mencakup X. Set penutup itu sendiri bukan cara yang baik untuk melihat masalah ini, karena perkiraan masalah set penutup umum.

Satu-satunya alasan mengapa masalah ini tidak terlalu lambat menggunakan pendekatan serakah adalah karena simetri dalam kelompok permutasi membantu menghilangkan banyak redundansi. Khususnya, jika S adalah subkelompok, dan T adalah subset kecil yang merupakan himpunan penutup minimal, maka himpunan sT (kalikan T dengan elemen grup s) masih dalam S dan masih merupakan himpunan penutup (tentu saja dari ukuran yang sama, jadi masih minimal.) Jika Anda bertanya-tanya, kasus yang berhasil memiliki n ~ 30 dan | S | ~ 1000, dengan hasil yang serakah beruntung memiliki | T | ~ 37. Kasing dengan n ~ 50 memiliki beberapa batasan yang sangat buruk yang membutuhkan waktu sangat lama untuk didapatkan.

Untuk meringkas, saya bertanya-tanya apakah ada pendekatan pendekatan untuk masalah ini atau apakah itu masih cukup umum untuk masuk dalam beberapa teorema ketidaksesuaian seperti ada untuk masalah set penutup umum. Algoritma apa yang digunakan untuk memperkirakan masalah terkait dalam praktiknya? Sepertinya ada sesuatu yang mungkin karena himpunan bagian semua ukuran yang sama dan setiap elemen muncul pada frekuensi kecil yang sama 1 / n.

-B

Berikut adalah analisis hampir ketat approximability untuk kasus di mana S adalah tidak diperlukan untuk menjadi subkelompok dari kelompok simetris.

Masalah ini adalah kasus khusus dari Set Cover, dan ada algoritma pendekatan serakah sederhana [Joh74]. Jika kita menyatakan k th nomor harmonis sebagai H _k = Σ _{i = 1} ^k 1 / i , algoritma serakah mencapai rasio perkiraan H _n = ln n + Θ (1). (Ada algoritma [DF97] yang menghasilkan rasio aproksimasi yang sedikit lebih baik H _n −1/2.) ( Edit : Revisi 2 dan sebelumnya menyatakan rasio aproksimasi dari algoritma serakah lebih buruk daripada nilai yang benar.)

Selain itu, ini hampir optimal dalam arti sebagai berikut:

Teorema . Set Cover untuk Permutasi Matriks tidak dapat didekati dalam rasio aproksimasi (1− ε ) ln n untuk konstanta 0 < ε <1 kecuali NP ⊆ DTIME ( n ^{O (log log n )} ).

Ini adalah sketsa bukti. Kami menulis [ n ] = {1,…, n }. Kami akan membuat pengurangan dari Set Cover:

Set Cover
Instance : Bilangan bulat positif m dan koleksi C himpunan bagian dari [ m ].
Solusi : Subset D dari C sedemikian sehingga penyatuan set dalam D sama dengan [ m ].
Tujuan : Minimalkan | D |.

Ini adalah hasil terkenal oleh Feige [Fei98] bahwa Set Cover tidak dapat didekati dalam rasio aproksimasi (1− ε ) ln m untuk konstanta 0 < ε <1 kecuali NP ⊆ DTIME ( n ^{O (log log n )} ).

Biarkan ( m , C ) menjadi instance dari Set Cover. Kami akan membuat instance ( n , S ) dari Set Cover untuk Permutasi Matriks.

$\pmatrix{0 & 1 \\ 1 & 0}$$\pmatrix{1 & 0 \\ 0 & 1}$i ≤ n (di mana indeks i +2 ditafsirkan sebagai modulo n ). Untuk 0≤ j ≤ m , tentukan S _j = { P _E Q ^j : E ∈ C ∪ {{ m +1}}} dan S = S ₀ ∪… ∪ S _m .

Klaim . Biarkan k menjadi ukuran penutup minimal [ m ] di C . Maka ukuran tutup minimum dalam S sama dengan ( k +1) ( m +1).

Sketsa bukti . Jika D ⊆ C adalah sampul [ m ], kita dapat membuat sampul T ⊆ S ukuran (| D | +1) ( m +1) oleh T = { P _E Q ^j : E ∈ S ∪ {{ m +1}}, 0≤ j ≤ m }.

Di sisi lain, biarkan T ⊆ S menjadi penutup. Perhatikan bahwa semua matriks dalam S ₀ adalah blok diagonal dengan blok berukuran 2 × 2, dan matriks lain di S memiliki 0 pada blok ini. Oleh karena itu, T ∩ S ₀ mencakup blok-blok ini. Selain itu, T ∩ S ₀ berisi P _{{ m +1}} karena jika tidak (2 m +1, 2 m +2) -tidak akan dicakup. Perhatikan itu ( T ∩ S ₀ ) ∖ { P _{{ m +1}}} Sesuai dengan penutup set di C . Oleh karena itu, | T ∩ S ₀ | ≥ k +1. Demikian pula, untuk 0≤ j ≤ m , | T ∩ S _j | ≥ k +1. Oleh karena itu, | T | ≥ ( k +1) ( m +1). Sketsa akhir bukti Klaim .

Dengan Klaim, pengurangan yang dibuat di atas mempertahankan rasio perkiraan. Secara khusus, itu menetapkan teorema.

Referensi

[DF97] Rong-Chii Duh dan Martin Fürer. Perkiraan tutupan k- set dengan optimisasi semi-lokal. Dalam Prosiding Simposium ACM Tahunan Dua Puluh Sembilan tentang Teori Komputasi (STOC) , hlm. 256–264, Mei 1997. http://dx.doi.org/10.1145/258533.258599

[Fei98] Uriel Feige. Ambang batas ln n untuk perkiraan penutup yang ditetapkan. Jurnal ACM , 45 (4): 634-652, Juli 1998. http://dx.doi.org/10.1145/285055.285059

[Joh74] David S. Johnson. Algoritma pendekatan untuk masalah kombinatorial. Jurnal Ilmu Komputer dan Sistem , 9 (3): 256–278, Desember 1974. http://dx.doi.org/10.1016/S0022-0000(74)80044-9

Saat makan siang di Brussels kami membuktikan bahwa masalah ini adalah NP-Hard dengan pengurangan yang cukup singkat dari 3SAT. Bukti kami tidak mengarah pada hasil yang tidak dapat diperkirakan (belum). Kami akan memikirkannya lebih lanjut.

Secara kasar, Anda mentransformasikan instance 3-SAT (dengan n variabel dan klausa c) menjadi serangkaian permutasi yang terstruktur sebagai berikut:

1 ... n untuk penomoran n variabel n + 1 digunakan oleh gadget variabel n + 2, n + 3 mewakili klausa pertama ... n + 2j, n + 2j + 1 mewakili klausa j n + 2c + 2 digunakan oleh pemulung

variabel xi diwakili oleh permutasi 1, ..., i-1, n +1, i + 1, ..., n, i, ... dan menukar n + 2j + 1, n + 2j untuk setiap klausa di mana j di mana xi muncul; dan permutasi 1, ..., i-1, n + 1, i +1, ..., n, i, ... dan menukar n + 2j + 1, n + 2j untuk setiap klausa di mana j di mana - xi muncul.

Kemudian kami menggunakan pengumpul sampah untuk menempatkan setiap angka di posisi yang tidak dapat ditampilkan sebaliknya. Untuk menempatkan x di posisi y, kami menempatkan y di posisi n + 2c + 2 dan n + 2c + 2 di posisi x. Kami akan memiliki n + 2c-1 pengumpul sampah seperti itu untuk setiap variabel dan 2 (n + 2c-1) untuk setiap klausa. 3SAT memuaskan jika kita dapat memilih tepat satu dari 2 permutasi untuk setiap variabel, jika penutup permutasi memiliki solusi ukuran n + (n + 2c-1) (n + 2c).

Mungkin ada beberapa detail kecil yang hilang untuk contoh kecil.

Stefan.