Konsensclustering unter Verwendung der Mengenunion

Ich habe diese Frage bereits vor einiger Zeit auf MathOverflow gepostet , aber meines Wissens ist sie immer noch offen. Deshalb veröffentliche ich sie hier in der Hoffnung, dass jemand davon gehört hat.

Problemstellung

Lassen , Q und R drei Trennwände in seiner p nicht leeren Teile (bezeichnet P h 's, Q i ' s und R j des Satzes s) { 1 , 2 , ... , n }. Finden Sie zwei Permutationen π und σ , die p ∑ i = 1 | minimieren 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|.$$

Fragen

1) Wie komplex ist dieses Problem (oder das entsprechende Entscheidungsproblem)?

2) Wenn das Problem tatsächlich in Polynomzeit lösbar ist, bleibt es für eine beliebige Anzahl von Partitionen wahr ?$k\geq 4$

Vorherige Arbeit

Berman, DasGupta, Kao und Wang ( http://dx.doi.org/10.1016/j.ipl.2007.06.008 ) untersuchen ein ähnliches Problem für Partitionen, verwenden jedoch paarweise Δs anstelle von ∪ in der obigen Summe. Sie beweisen, dass das Problem für k = 3 MAX-SNP-schwer ist , selbst wenn jedes Teil nur zwei Elemente enthält, indem sie MAX-CUT auf kubische Graphen auf einen speziellen Fall ihres Problems reduzieren und a ( 2 - 2 / k angeben ) -Näherung für beliebige k . Bisher konnte ich mein Problem nicht in der Literatur finden oder deren Beweis anpassen.$k$$\Delta$$\cup$$k=3$$(2-2/k)$$k$

Einfache Unterfälle

Hier sind einige Unterfälle, bei denen ich festgestellt habe, dass sie in der Polynomzeit lösbar sind:

• der Fall ;$k=2$
• der Fall für irgendein k ;$p=2$$k$

Wenn außerdem , keine zwei Teile gleich sind und alle Teile die Größe 2 haben , haben wir die untere Schranke 3 p + 1 (ich weiß nicht, ob es eng ist).$k=3$$2$$3p+1$

Das Problem ist NP-schwer. Beweis ist durch Reduktion von folgendem Problem:

Gibt es bei einem dreigliedrigen Graphen mit N Ecken in jedem Teil N vertex-disjunkte Dreiecke in G ?$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$