Grupowanie konsensusowe za pomocą ustawionej unii

Zadałem już to pytanie jakiś czas temu na MathOverflow , ale zgodnie z moją najlepszą wiedzą jest ono nadal otwarte, więc zamieszczam je ponownie w nadziei, że ktoś o nim usłyszy.

Opis problemu

Niech , i będą trzema partycjami w niepustych częściach (oznaczonych przez , i ) zestawu { }. Znajdź dwie kombinacje i które minimalizująQ R p P h Q i R j 1 , 2 , … , n π σ 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|.$$

pytania

1) Jaka jest złożoność tego problemu (lub odpowiadającego mu problemu decyzyjnego)?

2) Jeśli problem da się rozwiązać w czasie wielomianowym, czy pozostaje on prawdą dla dowolnej liczby partycji?$k\geq 4$

Poprzednia praca

Berman, DasGupta, Kao i Wang ( http://dx.doi.org/10.1016/j.ipl.2007.06.008 ) badają podobny problem dla partycji , ale używając par zamiast w powyższym suma. Udowadniają, że problem jest trudny dla MAX-SNP dla , nawet gdy każda część ma tylko dwa elementy, redukując MAX-CUT na wykresach sześciennych do specjalnego przypadku ich problemu, i dają - przybliżenie dla dowolnego . Jak dotąd nie udało mi się znaleźć problemu w literaturze ani dostosować ich dowodów.Δ ∪ k = 3 ( 2 - 2 / k ) $k$$\Delta$$\cup$$k=3$$(2-2/k)$$k$

Łatwe podklasy

Oto niektóre podklasy, które można rozwiązać w czasie wielomianowym:

• przypadek ;$k=2$
• przypadek dla dowolnego ;$p=2$$k$

Ponadto, gdy , żadne dwie części nie są równe, a wszystkie części mają rozmiar , mamy dolną granicę 3 p + 1 (nie wiem, czy jest ciasno).$k=3$$2$$3p+1$

Problem jest trudny NP. Dowodem jest redukcja z następującego problemu:

Biorąc pod uwagę trójstronny wykres z N wierzchołkami w każdej części, czy istnieje N trójkątów rozłącznych w G w G ?$G$$N$$N$$G$

Oto redukcji: podany wystąpienie powyższego problemu, niech A 1 , 2 , 3 oznacza zbiór wierzchołków w każdej z części G , i E i J jest zestaw krawędzi między A ı i A j . Również liczba wierzchołków w każdą część 1 , ... , N .$G$$A_1$$A_2$$A_3$$G$$E_{ij}$$A_i$$A_j$$1,\dotsc,N$

Tworzymy wystąpienie twojego problemu za pomocą , gdzie M jest dużą liczbą (powiedzmy, M = 10 | E ( G ) | ), a p = N + 1 . Pierwszy | E ( G ) | Elementy { 1 , ... , n } odpowiadają krawędzi G . Partycja P jest zdefiniowana następująco:$n = |E(G)| + M$$M$$M = 10 |E(G)|$$p = N + 1$$|E(G)|$$\{1,\dotsc,n\}$$G$$P$ z i = 1 , ... , N jest zestaw krawędzi, które mają ı th wierzchołek A 1, jako jednego z punktów końcowych. Oczywiście te zbiory są rozłączne, a ich związek wynosi E 1 , 2 ∪ E 1 , 3 . P N + 1 to wszystko inne, tj. E 2 , 3 ∪ { | E ( G ) | + 1 , … , | $P_i$$i=1,\dotsc,N$$i$$A_1$$E_{1,2} \cup E_{1,3}$$P_{N+1}$ . Podobnie, określenie P stosując A 2 zamiast A 1 , a R przy użyciu A 3 zamiast A 1 .$E_{2,3} \cup \{|E(G)| + 1, \dotsc, |E(G)| + M\}$$Q$$A_2$$A_1$$R$$A_3$$A_1$

Twierdzimy teraz, że ten przypadek ma rozwiązanie kosztujące najwyżej wtedy i tylko wtedy, gdy G ma N rozłącznych trójkątów. Aby to zobaczyć, najpierw zauważ, że ponieważ M jest duże, każde rozwiązanie, które kosztowało mniej niż 2 M, musi odwzorować P N + 1 na Q N + 1 i R N + 1 . To już stanowi | E ( G ) $3|E(G)| - 3N + M$$G$$N$$M$$2 M$$P_{N+1}$$Q_{N+1}$$R_{N+1}$ całkowitego kosztu, więc zostaje nam 2 | E ( G ) | - 3 N . Zauważmy teraz, że przecięcie każdego P i każdego Q j jest co najwyżej jeden (i podobnie dla P i i R k , a także dla Q j i R k ). Tak więc funkcja celu jest zminimalizowana, jeśli wszystkie te przecięcia mogą być równe 1 w tym samym czasie. Odpowiada to N rozłącznych trójkąty G .$|E(G)| + M$$2 |E(G)| - 3 N$$P_i$$Q_j$$P_i$$R_k$$Q_j$$R_k$$N$$G$