Pengelompokan konsensus menggunakan set union

Saya sudah memposting pertanyaan ini beberapa waktu yang lalu di MathOverflow , tapi sejauh pengetahuan saya masih terbuka, jadi saya memposting ulang di sini dengan harapan bahwa seseorang mungkin pernah mendengarnya.

Pernyataan masalah

Misalkan , Q dan R menjadi tiga partisi menjadi p bagian yang tidak kosong (dilambangkan dengan P h , Q i dan R j ) dari himpunan { 1 , 2 , … , n }. Temukan dua permutasi π dan σ yang meminimalkan p ∑ i = 1 | P i ∪ Q π i ∪ R σ i | $P$$Q$$R$$p$$P_h$$Q_i$$R_j$$1,2,\ldots,n$$\pi$$\sigma$

$$\sum_{i=1}^p\left|P_i\cup Q_{\pi_i}\cup R_{\sigma_i}\right|.$$

Pertanyaan

1) Apa kompleksitas masalah ini (atau masalah keputusan terkait)?

2) Jika masalah memang dapat dipecahkan dalam waktu polinomial, apakah itu tetap berlaku untuk angka partisi?$k\geq 4$

Pekerjaan sebelumnya

Berman, Dasgupta, Kao dan Wang ( http://dx.doi.org/10.1016/j.ipl.2007.06.008 ) mempelajari masalah yang sama untuk partisi, tetapi menggunakan berpasangan Δ 's bukan ∪ dalam jumlah di atas. Mereka membuktikan bahwa masalahnya adalah MAX-SNP-hard untuk k = 3 , bahkan ketika setiap bagian hanya memiliki dua elemen, dengan mengurangi MAX-CUT pada grafik kubik ke kasus khusus masalah mereka, dan memberikan ( 2 - 2 / k ) -Aproksimasi untuk k . Sejauh ini, saya belum dapat menemukan masalah saya dalam literatur, atau untuk mengadaptasi bukti mereka.$k$$\Delta$$\cup$$k=3$$(2-2/k)$$k$

Sub-bagian mudah

Berikut adalah beberapa sub-bagian yang menurut saya dapat dipecahkan dalam waktu polinomial:

• kasing ;$k=2$
• case , untuk setiap k ;$p=2$$k$

Selain itu, ketika , tidak ada dua bagian yang sama dan semua bagian memiliki ukuran 2 , kita memiliki batas bawah 3 p + 1 (saya tidak tahu apakah itu kencang).$k=3$$2$$3p+1$

Masalahnya adalah NP-hard. Bukti dengan reduksi dari masalah berikut:

$G$$N$$N$$G$

$G$$A_1$$A_2$$A_3$$G$$E_{ij}$$A_i$$A_j$$1,\dotsc,N$

$n = |E(G)| + M$$M$$M = 10 |E(G)|$$p = N + 1$$|E(G)|$$\{1,\dotsc,n\}$$G$$P$$P_i$$i=1,\dotsc,N$$i$$A_1$$E_{1,2} \cup E_{1,3}$$P_{N+1}$$E_{2,3} \cup \{|E(G)| + 1, \dotsc, |E(G)| + M\}$$Q$$A_2$$A_1$$R$$A_3$$A_1$

$3|E(G)| - 3N + M$$G$$N$$M$$2 M$$P_{N+1}$$Q_{N+1}$$R_{N+1}$$|E(G)| + M$$2 |E(G)| - 3 N$$P_i$$Q_j$$P_i$$R_k$$Q_j$$R_k$$N$$G$