Bagaimana meminimalkan kardinalitas suatu set dan memisahkan partisi yang mengalami kendala dalam waktu polinomial?

Masalah sebenarnya yang saya hadapi adalah sebagai berikut.

INSTAN : Saya telah menetapkan dan dan matrix untuk semua dan .$N:=\{1,\ldots,n\}$$K:=\{1,\ldots,k\}$$a_{ij}>0$$i\in K$$j\in N$

PERTANYAAN : Saya harus mencari subset dari ukuran sekecil mungkin dan partisi set dalam menetapkan yang persatuannya sama dengan sehingga untuk semua , saya memiliki untuk semua i \ dalam K_j .$S$$N$$K$$|S|$$K_j$$K$$j\in S$

$$\sum_{j'\in S\\j'\neq j} a_{ij'} \leqslant a_{ij}-1,$$ $i\in K_j$

Contoh:

Diberikan $n=k=3$ dan matriks

$$\begin{bmatrix} 0.6 & 2.7 & 1.2\\ 1.3 & 2.6 & 0.8\\ 1.5 & 0.4 & 0.6 \end{bmatrix}.$$

Dalam contoh ini, $S$ harus sama dengan $S=\{1, 2\}$ dan $K_1=\{3\}$ dan $K_2=\{1,2\}$ .

Saya memperhatikan dua fakta:

• Jika ada beberapa $j\in N$ sehingga $a_{ij}\geqslant 1$ untuk semua $i\in K$ maka $S=\{j\}$ dan $K_j=K$ ; dan
• Jika ada beberapa $i\in K$ sehingga $a_{ij}<1$ maka $S=\emptyset$ .

Pertanyaan saya : Apakah mungkin untuk menyelesaikan masalah optimisasi ini dalam waktu polinomial (setidaknya dengan algoritma aproksimasi)?

Hal pertama yang saya coba lakukan adalah mengubahnya menjadi masalah yang diketahui dan kemudian menerapkan algoritma yang dikenal untuk itu. Saya berpikir untuk mengubahnya menjadi penutup atau nampan pengepakan tetapi saya gagal dan juga saya tidak berpikir bahwa ini menarik.

---

Masalah yang saya coba rumuskan.

Saya memiliki set dan dan matriks untuk semua dan . Juga, saya memiliki disjoints menetapkan untuk setiap , (saya menambahkan sebagai input karena saya tidak bisa memformulasikannya sebaliknya.)$N:=\{1,\ldots,n\}$$K:=\{1,\ldots,k\}$$a_{ij}>0$$i\in K$$j\in N$$n$$K_j\subset K$$j\in N$$K_j$

Akhirnya, saya mendapatkan ini:

$$\begin{align*} & {\underset{S}{\text{minimize}}} & & |S|\\[3pt] & \text{subject to} & & \sum_{j'\in S\\j'\neq j} a_{ij'} \leqslant a_{ij}-1,\forall\, j\in S,i\in K_j,\\[3pt] & & & S\subseteq N.\\ \end{align*}$$

Terima kasih.

Bahkan versi keputusan dari masalah ini, yang kami coba tentukan hanya jika ada solusi yang layak, adalah NP-hard dengan reduksi dari Exact Cover . (Versi optimisasi, di mana kami mencari solusi yang layak yang meminimalkan , jelas setidaknya sama sulitnya dengan ini.)$|S|$

Matriks baris tunggal, kolom tunggal yang berisi nilai 0,5 adalah contoh input yang tidak ada solusi yang layak. Ini yang lain:

$$\begin{bmatrix} 0.2 & 4\\ 3.1 & 3\\ 5 & 0.6 \end{bmatrix}.$$

Membuat gadget "Pilih paling banyak satu"

Pertama, perhatikan bahwa jika nilai maksimum dalam beberapa baris adalah , dan baris ini berisi (setidaknya) dua salinan , katakan di dan , , lalu tidak dapat mengandung dan , karena jika itu terjadi maka salah satu dari dua kasus berikut harus muncul, yang masing-masing mengarah ke kontradiksi:$a_i$$x > 0$$x$$a_{ij}$$a_{ij'}$$j' \ne j$$S$$j$$j'$

1. $i \in K_j \cup K_{j'}$ : Misalkan wlog itu . Tapi kemudian , bertentangan dengan persyaratan bahwa .$i \in K_j$$\Sigma_{m \in S, m \ne j}{a_{im}} \ge a_{ij'} = x = a_{ij}$$\Sigma_{m \in S, m \ne j}{a_{im}} \le a_{ij} - 1$
2. $i \notin K_j \cup K_{j'}$ : Lalu misalkan . Tetapi kemudian , dan karena adalah maksimal pada baris , tertinggi bisa jelas , jadi kita harus melanggar ketimpangan yang sama seperti sebelumnya.$i \in K_p, p \notin \{j, j'\}$$\Sigma_{m \in S, m \ne p}{a_{im}} \ge a_{ij} + a_{ij'} = 2x$$x$$i$$a_{ip}$$x$

Dengan demikian kita dapat memilih beberapa nilai maksimum yang aman lebih tinggi dari jumlah semua nilai-nilai non-maksimum berturut-turut, dan penggunaan salinan nilai maksimum ini untuk menegakkan yang paling salah satu kolom termasuk dalam .$S$

Kita dapat mengubah batasan "pilih paling banyak satu" ini menjadi batasan "pilih tepat satu" dengan menggunakan nilai positif apa pun yang kurang dari 1 sebagai nilai "tidak maksimal". Itu karena setiap baris milik beberapa bagian dari partisi baris, dan jika maka RHS dari ketidaksetaraan menjadi negatif untuk baris , jadi tidak ada cara untuk memuaskannya: dengan demikian setidaknya satu harus dipaksa ke sedemikian rupa sehingga .$i$$K_j$$a_{ij} < 1$$i$$j$$S$$a_{ij} \ge 1$

Jadi, untuk memastikan bahwa salah satu kolom di beberapa set dipaksa ke , buat baris sebagai berikut:$T \subseteq N$$S$$a_i$

• Set untuk setiap .$a_{ij} = n+1$$j \in T$
• Set untuk setiap lainnya .$a_{ij} = 0.5$$j$

Dengan demikian pengurangan dari Exact Cover mudah: ada baris untuk setiap elemen, kolom untuk setiap set, dengan setiap kali set menyertakan elemen dan jika tidak. Kedua arah ("Input EC instance adalah instance-YA instance yang dibangun dari masalah OP adalah instance-YA", dan "instance Bangun masalah OP adalah instance-YA input instance EC adalah instance-YA") jelas.$a_{ij} = n+1$$j$$i$$a_{ij} = 0.5$$\implies$$\implies$