Maximieren der Summenkantengewichte

Ich frage mich, ob das folgende Problem einen Namen hat oder irgendwelche damit verbundenen Ergebnisse.

Sei $G = (V,w)$ ein gewichteter Graph, wobei das Gewicht der Kante zwischen und bezeichnet und für alle , . Das Problem besteht darin, eine Teilmenge von Eckpunkten zu finden, die die Summe der Gewichte der angrenzenden Kanten maximiert: Beachten Sie, dass ich Kanten zähle, die sowohl innerhalb der Teilmenge als auch außerhalb der Teilmenge liegen, was dieses Problem von Max-Cut unterscheidet. Selbst wenn sowohl u als auch v in S sind$w(u,v)$$u$$v$$u,v \in V$$w(u,v) \in [-1,1]$

Beachten Sie, dass das Problem trivial ist, wenn alle Kantengewichte nicht negativ sind - nehmen Sie einfach das gesamte Diagramm!

Nicht wirklich eine Lösung, aber einige Beobachtungen.

Dies ist ein Sonderfall des folgenden Problems: gegeben ein Universum und eine Sammlung von Mengen S 1 , … , S n ⊆ $U = \{1, \ldots, m\}$$S_1, \ldots, S_n \subseteq U$ und eine Gewichtsfunktion , finde die Menge I ⊆ [ n ] so, dass w ( ⋃ i ∈ I S i$w:U \rightarrow [-1, 1]$$I \subseteq [n]$$w(\bigcup_{i \in I}{S_i})$wird maximiert (das Gewicht eines Satzes ist das Gesamtgewicht seiner Elemente). Ihr Problem entspricht dem Fall, in dem jedes Element von in genau zwei Mengen vorkommt (aber ich bin nicht sicher, wie ich diese Einschränkung ausnutzen soll, obwohl dies hilfreich sein könnte).$U$

Dies ist ein Abdeckungsproblem: Ähnlich wie bei Max-k-Set-Cover, jedoch ohne die Einschränkung, Sätze zu verwenden und negative Gewichte zuzulassen. Die gierige Approximation von Max-k-Set-Cover (bei jedem Schritt wird die Menge ausgegeben, die das größte Gewicht an bisher nicht abgedeckten Elementen aufweist) gibt eine Folge von Mengen aus, so dass die ersten k Mengen eine 1 + 1 / e- Annäherung an die sind optimal (dies ist also eine simultane Näherung für alle k ). Leider gibt es wie üblich ein Problem bei der Analyse, wenn die Gewichte negativ sein können. Die grundlegende Beobachtung der Analyse des Greedy-Algorithmus ist, dass wenn S 1 die erste Menge ist, die ausgegeben wird, dann w $k$$k$$1 + 1/e$$k$$S_1$ ( O P T k ist das maximale Gewicht, das durch abgedeckt wird$w(S_1) \geq OPT_k/k$$OPT_k$ Sätzen), da O P T k kleiner ist als die Summe der Gewichte der k Sätze in der optimalen Lösung und jedes von sie haben ein Gewicht von weniger als w ( S 1 ) . Bei negativen Gewichten ist es jedoch nicht mehr wahr, dass O P T k kleiner ist als die Summe der Gewichte in der optimalen Lösung. Im Allgemeinen ist eine Gewerkschaftsbindung nicht mehr wahr.$k$$OPT_k$$k$$w(S_1)$$OPT_k$

FWIW, Ihr Problem ist innerhalb eines multiplikativen Faktors von für jedes ϵ > 0 schwer zu approximieren .$n^{1-\epsilon}$$\epsilon>0$

Wir zeigen dies im Folgenden, indem wir eine approximationserhaltende Reduktion aus Independent Set geben, für die die Approximationshärte bekannt ist.

Reduktion vom unabhängigen Satz

Der ungerichtete Graph sei eine Instanz der unabhängigen Menge. Lassen d v bezeichnen den Grad der Scheitelpunkt v in G . Lassen Sie n die Anzahl der Ecken in seiner G .$G=(V,E)$$d_v$$v$$G$$n$$G$

Konstruieren Sie den kantengewichteten Graphen aus G wie folgt. Gibt jede Kante in E Gewicht 1. Für jede nicht-isolierte Ecke v ∈ V , addieren d $G'=(V',E')$$G$$E$$v\in V$ neue Kanten,jeweils mitGewicht - 1 , bis d v - 1 neue Scheitelpunkte . Fügen Sie für jeden isolierten Scheitelpunkt v ∈ V eine neue Kante des Gewichts 1 zu einem neuen Scheitelpunkt hinzu.$d_v-1$$-1$$d_v-1$$v\in V$

(Hinweis: Jeder neue Scheitelpunkt (in aber nicht in G ) hat genau einen Nachbarn, nämlich in G. )$G'$$G$$G$

Lemma. hat eine unabhängige Menge der Größe k, wenn G ' (als Beispiel Ihres Problems) eine Wertlösung von mindestens k hat .$G$$k$$G'$$k$

Beweis. Lassen jeder unabhängige in seiner G . Da dann die Eckpunkte in S in G ' unabhängig sind , ist der Wert von S in G ' (durch Ihr Ziel) ∑ v ∈ S d v - ( d v - 1 ) = | S | $S$$G$$S$$G'$$S$$G'$

Umgekehrt sei eine Lösung für G ' mit einem Wert von mindestens k . Nehmen Sie ohne Verlust der Allgemeinheit an, dass S keine neuen Eckpunkte enthält. (Jede neue Eckpunkt v ' ist auf einer einzigen Kante ( v ' , v ) Ist. V nicht isoliert wurde , G , dann wird das Gewicht der Kante ist - 1 , so Entfernen v ' von S den Wert erhöht S . Wenn v isoliert wurde, dann ist das Gewicht der Kante 1, so dass v $S$$G'$$k$$S$$v'$$(v',v)$$v$$G$$-1$$v'$$S$$S$$v$$v'$von und Hinzufügen von v behält den Wert von S bei .)$S$$v$$S$

Nehmen Sie ohne Verlust der Allgemeinheit an, dass eine unabhängige Menge in G ist . (Andernfalls sei ( u , v ) eine Kante, so dass u und v in S sind . Das Gesamtgewicht der einfallenden Kanten von v in G ' ist d v - ( d v - 1 ) = 1 , also das Gesamtgewicht der einfallenden Kanten von v außer ( u , v ) ist höchstens Null. Somit wird $S$$G$$(u,v)$$u$$v$$S$$v$$G'$$d_v - (d_v-1) = 1$$v$$(u,v)$$v$von würde den Wert von S nicht erhöhen .)$S$$S$

Nun, durch die gleiche Berechnung wie zu Beginn des Beweises, der Wert von ist$S$. Daraus folgt, dass | S | ≥ k . QED$|S|$$|S| \ge k$

Nebenbei könnten Sie stattdessen nach einer additiven Näherung von beispielsweise oder ϵ m fragen . $O(n)$$\epsilon m$

Es scheint mir möglich, dass für Ihr Problem sogar die Entscheidung, ob es eine Lösung mit positivem Wert gibt, NP-schwer sein kann.