Złożoność problemu adopcji kociąt

To pojawiło się, gdy próbowałem odpowiedzieć na to pytanie dotyczące minimalizacji długości przewodów . Miałem to nazwać problemem „poligamicznego małżeństwa”, ale internet, tak kocięta. Tak!

Załóżmy, że mamy kociąt, które muszą być przyjęte przez ludzi, . Dla każdego kociaka, i każdej osoby kosztuje . Chcielibyśmy zminimalizować całkowity koszt przyjęcia wszystkich kociąt. Istnieje również szereg ograniczeń: każda osoba może adoptować nie więcej niż kocięta .N M > N i j c i j j u $M$$N$$M > N$$i$$j$$c_{ij}$$j$$u_j$

Bez ograniczeń problem jest prosty; każdy kotek idzie z osobą dla której jest minimalne. Czy z tymi ograniczeniami istnieje skuteczny algorytm dla tego problemu, czy jest to trudny NP?j c i $i$$j$$c_{ij}$

Jest to problem minimalnego kosztu maksymalnego przepływu.

Rozważmy wykres , gdzie jest zbiorem kociąt, jest zbiorem ludzi.A $G=(A\cup B\cup \{s,t\},E)$$A$$B$

Niech będzie pojemnością krawędzi, a będzie kosztem krawędzi. Dbamy o to c : E → R $C:E\to \mathbb{R}^+$$c:E\to \mathbb{R^+}$

1. Istnieje krawędź między , gdzie i , a , .a i ∈ A b j ∈ B C ( a i , b j ) = 1 c ( a i , b j ) = c i , $a_i,b_j$$a_i\in A$$b_j\in B$$C(a_i,b_j)=1$$c(a_i,b_j)=c_{i,j}$
2. Nie jest krawędź między i , a , .a i ∈ A C ( s , a i ) = 1 c ( s , a i ) = $s$$a_i\in A$$C(s,a_i)=1$$c(s,a_i)=0$
3. Nie jest krawędź między i , i , .$b_j\in B$$t$$C(b_j,t)=u_j$$c(b_j,t)=0$

Jeśli maksymalny przepływ wynosi , wiemy, że istnieje rozwiązanie. Z minimalnego kosztu maksymalnego można zbudować rozwiązanie o minimalnym koszcie.$M$

Jest to problem idealnego dopasowania minimalnej wagi, który jest wielomianowy. Rozważyć całkowite wykres dwustronnego , w którym L zawiera węzeł l I dla każdej kotek ı , R składa kształcie U j kopii węzła r j, dla każdej osoby, j , a krawędzie E i J ∈ E pomiędzy L i a każda kopia r j , o całkowitej masie C ı j .$(L , R , E)$$L$$l_i$$i$$R$$u_j$$r_{j}$$j$$e_{ij} \in E$$l_i$$r_{j}$$c_{ij}$

Wiemy to , w przeciwnym razie nie wszystkie kocięta mogą być przypisane do osób.$|L| \leq |R|$

Ponieważ idealne dopasowanie musi dopasować wszystkie węzły, musimy dodać obojętne węzłów do (aby dostać | L | = | R | ) i połączyć je z zerowym krawędziach wagi do wszystkich węzłów w R .$L$$|L| = |R|$$R$

Być może interesujące jest spostrzeżenie, że można zredukować Partycję do wariantu tego problemu. Podana jest instancja partycji z elementami z q, nawet z której musimy wybrać podzbiór S ⊆ { 1 , … , q } z | S | = q / 2 takie, że ∑ i ∈ S x i = ∑ i ∉ S x i = $\{x_1,\dots,x_q\}$$q$$S \subseteq \{1,\dots,q\}$$|S|=q/2$$\sum_{i\in S} x_i = \sum_{i\not\in S} x_i = K$. (Pamiętaj, że wymóg wybrania dokładnie połowy elementów nie jest zwykłą formą, ale ta forma jest wciąż trudna do NP). Niech każdy kotek będzie elementem zestawu; niech będą dwie osoby; niech wagi będą wynosić oraz c i 2 = - x i ; niech u 1 = u 2 = q / 2 . Następnie ten przypadek kociąt Przyjęcie ma maksimum w 0 IFF wystąpienie strefowych roztworu.$c_{i1} = x_i$$c_{i2} = -x_i$$u_1 = u_2 = q/2$$0$

Jeśli koszty adopcji kociąt mają być zawsze dodatnie, można po prostu dodać wystarczająco dużą stałą do wszystkich wag, aby upewnić się, że są one właściwym znakiem, gdy wymagany próg to C q zamiast 0.$C$$Cq$

Nie jestem pewien, co to mówi o złożoności pierwotnego problemu, ale biorąc pod uwagę często spotykany „jeden z minimalizacji / maksymalizacji jest NP-trudny, drugi jest w konfiguracji P” dla kombinatorycznych problemów optymalizacji, zacznę szukać wydajny algorytm.