Maksymalizacja sumarycznych wag krawędzi

Zastanawiam się, czy następujący problem ma nazwę lub wyniki z nim związane.

Niech będzie wykresem ważonym, gdzie oznacza wagę krawędzi między i , a dla wszystkich , . Problem polega na znalezieniu podzbioru wierzchołków, który maksymalizuje sumę wag sąsiadujących z nimi krawędzi: Zauważ, że liczę krawędzie, które są wewnątrz podzbioru i które znajdują się poza podzbiorem, co odróżnia ten problem od maksymalnego cięcia. Jednak nawet jeśli zarówno jak i są w , chcę tylko policzyć krawędź $G = (V,w)$ $w(u,v)$ $u$ $v$ $u,v \in V$ $w(u,v) \in [-1,1]$

max_{S \subseteq V} \sum_{(u, v) : u \in S or v \in S} w (u, v)

$\max_{S \subseteq V} \sum_{(u,v) : u \in S\ \textrm{or}\ v\in S} w(u,v)$

u

$u$

v

$v$

S

$S$

(u, v)

$(u,v)$ jeden raz (a nie dwa razy), co odróżnia cel od zwykłego bycia sumą stopni.

Zauważ, że problem jest trywialny, jeśli wszystkie grubości krawędzi nie są ujemne - po prostu weź cały wykres!

— Aaron Roth
źródło

Twoja definicja nie zgadza się później z twoją notatką o nieliczaniu zduplikowanych krawędzi. Czy sumujesz nad uporządkowanymi parami lub podzbiorami 2-elementowymi? (ten ostatni zapewniłby ci potrzebną nieruchomość, tak myślę)

— Suresh Venkat

Kolejna uwaga: jedynymi wagami NIE obliczonymi są te wewnątrz V \ S. Czy jesteś zainteresowany wynikami twardości lub przybliżeniami, ponieważ w pierwszym przypadku minimalizacja sumy wag krawędzi wewnątrz S '= V \ S może być bardziej naturalnym problemem .

— Suresh Venkat

@Suresh: Formalna definicja w pytaniu jest poprawna, o ile dotyczy to przybliżenia. To daje dokładnie dwa razy więcej, niż można się spodziewać po słowach.

— Tsuyoshi Ito

@TsuyoshiIto: och, rozumiem, ponieważ krawędzie w poprzek cięcia są również liczone dwukrotnie.

— Suresh Venkat

Dokładny problem to NP-trudny, ponieważ, jak napisał Suresh w swoim komentarzu, problem jest równoważny nieograniczonemu programowi {0,1}, który jest NP-trudny.

— Tsuyoshi Ito

Odpowiedzi:

Nie do końca rozwiązanie, ale pewne spostrzeżenia.

Jest to szczególny przypadek następującego problemu: biorąc pod uwagę wszechświat i zbiór zestawów , oraz funkcję wagi , znajdź zbiór taki, że jest zmaksymalizowany (waga zestawu jest całkowitą wagą jego elementów). Twój problem odpowiada przypadkowi, w którym każdy element pojawia się w dokładnie dwóch zestawach (ale nie jestem pewien, jak wykorzystać to ograniczenie, chociaż może to pomóc). $U = \{1, \ldots, m\}$ $S_1, \ldots, S_n \subseteq U$ $w:U \rightarrow [-1, 1]$ $I \subseteq [n]$ $w(\bigcup_{i \in I}{S_i})$ $U$

Jest to problem pokrycia: podobny do Max-k-Set-Cover, ale bez ograniczenia używania zestawów i dozwolonych ujemnych wag. Chciwe przybliżenie Max-k-Set-Cover (na każdym kroku wyprowadza zestaw, który do tej pory ma największą wagę odsłoniętych elementów), generuje sekwencję zestawów, tak że pierwsze zestawów jest przybliżeniem do optimum (więc jest to równoczesne przybliżenie dla wszystkich ). Niestety, jak zwykle, istnieje problem z analizą, gdy wagi mogą być ujemne. Podstawowa obserwacja analizy chciwego algorytmu jest taka, że jeśli jest pierwszym zestawem wyjściowym, to ( $k$ $k$ $1 + 1/e$ $k$ $S_1$ $w(S_1) \geq OPT_k/k$ $OPT_k$ jest to maksymalna waga objęta zestawów), ponieważ jest mniejsza niż suma wag zestawów w optymalnym rozwiązaniu, a każdy z nich ma wagę mniejszą niż . Jednak przy ujemnych wagach nie jest już prawdą, że jest mniejsze niż suma wag w optymalnym rozwiązaniu. Ogólnie rzecz biorąc, związek zawodowy nie jest już prawdziwy. $k$ $OPT_k$ $k$ $w(S_1)$ $OPT_k$

— Sasho Nikolov
źródło

FWIW, twój problem jest trudny do oszacowania w ramach mnożnika dla dowolnego . $n^{1-\epsilon}$ $\epsilon>0$

Pokazujemy to poniżej, podając zachowującą aproksymację redukcję z zestawu niezależnego, dla którego znana jest twardość aproksymacji.

Redukcja z zestawu niezależnego

Niech niekierowany wykres będzie instancją Zestawu Niezależnego. Niech oznaczają stopień wierzchołka w . Niech jest liczbą wierzchołków . $G=(V,E)$ $d_v$ $v$ $G$ $n$ $G$

Skonstruuj wykres ważony na krawędzi z w następujący sposób. Daj każdej krawędzi wagę 1. Dla każdego nieizolowanego wierzchołka dodaj nowe krawędzie, każdy o wadze , do nowych wierzchołków. Dla każdego izolowanego wierzchołka dodaj jedną nową krawędź wagi 1 do nowego wierzchołka. $G'=(V',E')$ $G$ $E$ $v\in V$ $d_v-1$ $-1$ $d_v-1$ $v\in V$

(Uwaga: każdy nowy wierzchołek (w ale nie w ) ma dokładnie jednego sąsiada, który jest w ] $G'$ $G$ $G$

Lemat. ma niezależny zestaw wielkości iff (jako przykład twojego problemu) ma rozwiązanie o wartości co najmniej . $G$ $k$ $G'$ $k$

Dowód. Niech być każdy niezależny zestaw w . Zatem, ponieważ wierzchołki w są niezależne w , wartość w (według twojego celu) wynosi $S$ $G$ $S$ $G'$ $S$ $G'$

\sum_{v \in S} d_{v} - (d_{v} - 1) = | S | .

$\sum_{v\in S} d_v - (d_v-1) ~=~ |S|.$

I odwrotnie, niech będzie rozwiązaniem dla o wartości co najmniej . Bez utraty ogólności załóżmy, że nie zawiera żadnych nowych wierzchołków. (Każdy nowy wierzchołek znajduje się na pojedynczej krawędzi . Jeśli nie było izolowane w , to waga krawędzi wynosi , więc usunięcie z zwiększa wartość Jeśli został wyizolowany, a następnie waga krawędzi wynosi 1, więc usunięcie z i dodanie zachowuje wartość ). $S$ $G'$ $k$ $S$ $v'$ $(v',v)$ $v$ $G$ $-1$ $v'$ $S$ $S$ $v$ $v'$ $S$ $v$ $S$

Bez utraty ogólności, zakłada się, że jest niezależny zestaw w . (W przeciwnym razie, niech będzie taką krawędzią, że i są w Całkowita waga krawędzi padających w wynosi , więc całkowita waga krawędzie zdarzenia inne niż wynoszą co najwyżej zero. Zatem usunięcie z nie zwiększyłoby wartości ). $S$ $G$ $(u,v)$ $u$ $v$ $S$ $v$ $G'$ $d_v - (d_v-1) = 1$ $v$ $(u,v)$ $v$ $S$ $S$

Teraz, według tych samych obliczeń, co na początku dowodu, wartość wynosi. Wynika z tego, że . CO BYŁO DO OKAZANIA $S$ $|S|$ $|S| \ge k$

Na marginesie, możesz zamiast tego poprosić o przybliżenie addytywne , powiedzmy lub . $O(n)$ $\epsilon m$

Wydaje mi się możliwe, że dla twojego problemu nawet podjęcie decyzji, czy istnieje rozwiązanie o wartości dodatniej, może być trudne NP.

— Neal Young
źródło