Lokale Suche und Approximation

Question

Guten Abend Deutschland, Guten Morgen aus Tralien,

im Folgenden eine extremst schwere Aufgabe, bei der ich mir momentan die Köpfe ausbeiße (oder so ähnlich...) räusper

Aufgabe:
Gegeben sei ein bipartiter Graph G= (V1 ∪V2, E) mit V1 ∩ V2= ∅und E⊆ V1×V2 sowie eine Gewichtsfunktion w:E→R. Gesucht ist ein Matching maximalen Gewichts. Das Gewicht eines MatchingsM ist die Summe der Gewichte der enthaltenen Kanten. Zu einem Matching M definierenwir die k-Flip Umgebung als

N_k (M) :={M′: |(M′ \ M) ∪ (M\M′) ∣ ≤k}.

Die lokale Suche mit der k-Flip Umgebung erlaubt den Übergang von einem Matching M zu einemMatching aus N_k(M). Zeige folgende Aussagen:

a) Strikte lokale Suche mit 2-Flip Umgebung für gewichtetes bipartites Matching hat keinenkonstant beschränkten Approximationsfaktor.

b) Strikte lokale Suche mit 3-Flip Umgebung hat einen Approximationsfaktor von höchstens 2.

c) Strikte lokale Suche mit 3-Flip Umgebung hat einen Approximationsfaktor von mindestens 2.

Ansatz
Soweit, so (un-)gut. Ich stelle mir M und M' als 2 unterschiedliche Mengen vor, wo bei die Elemente nun über Kanten verbunden werden können. Dabei darf es keine Verbindungen zwischen den Elementen von M bzw. zwischen den Elementen von M' untereinander geben.

Als Beispiel habe ich M mit 4 Elementen und M' mit 3 Elementen. Eine lokale Suche würde im 1. Anlauf die Elemente so verbinden, dass alle Elemente auf M mit einem aus M' verknüpft sind, aber nicht jeder Knoten ein bipartites Matching hat.

z.b. M besteht aus {1,2,3,4} und M' aus {a,b,c}. Die Verknüpfungen sind {1,a}, {1,b}, {2,b}, {2,c}, {3,b}, {4c}.

Dann wäre ein bipartites Matching z.b. {1,b}, {2c}. Aber man könnte durch k = 2 Operationen (Kante entfernen, Kante einfügen) erkennen das es noch ein viel besseres bipartites Matching geben kann, nämlich {1,a}, {2,b}, {4,c}. Genau so gut könnte man auch {1,a}, {3,b}, {2,c} nehmen. Ist das ein korrekter Beweis für 2-Flip-Umgebung? Und wie zeig ich damit mathematisch korrekt, dass keinen Approximationsfaktor von 2 gibt?

Comments

Ich stelle mir M und M' als 2 unterschiedliche Mengen vor, wo bei die Elemente nun über Kanten verbunden werden können.

Mach das nicht.

Stelle dir stattdessen M und M' als zwei Matchings vor, bei denen sich M' von M dadurch unterscheidet, dass gegenüber M höchstens k Veränderungen (d.h. Kante entfernen, Kante einfügen) vorgenommen wurden.

Answer 1

Ein Beispiel

• V₁ = {1,2,3},
• V₂ = {4,5},
• E = {(1,4), (1,5), (2,4), (2,5), (3,5)},
• w: (a,b) ↦ a·b,
• M = { (1,4), (2,5) }

Dann ist N₂(M) = { ∅, {(1,4)}, {(2,5)}, {(1,4), (3,5)}, M }

Ferner sei

        W: Pot(E) → ℝ, K ↦ ∑_m∈K w(m)

die Funktion, die jedem Matching sein Gewicht zuordnet.

Dann ist

        W(M) = w((1,4)) + w((2,5)) = 1·4 + 2·5 = 14.

Für die Elemente aus N₂(M) ergeben sich folgende Gewichte:

• W(∅) = 0
  
• W({(1,4)}) = 4
• W({(2,5)}) = 10
• W({(1,4), (3,5)}) = 19

Laut strikter lokaler Suche wird also mit dem Matching {(1,4), (3,5)} weiter gesucht.

a) Strikte lokale Suche mit 2-Flip Umgebung für gewichtetes bipartites Matching hat keinenkonstant beschränkten Approximationsfaktor.

Konstruiere einen bipartiten Graphen, eine Gewichtsfunktion auf den Kanten des Graphen und ein Matching M auf dem Graphen, so dass zwei Kanten aus M entfernt werden müssen, damit eine in der Summe bessere Kante hinzugefügt werden kann.

Comments

Danke für die Antwort, aber ich verstehe es gerade leider nicht so wirklich, worauf du hinauswillst. Ich soll jetzt einen Graphen konstruieren, so dass das 2 Kanten entfern werden und dafür eine größere Kante hinzugefügt werden muss. Also angenommen,

    V1 = {1,2,3,1000},
    V2 = {5,6,7},
    E = {(1,5), (1,6), (1,7), (2,5), (2,6), (2,7), (3,5), (3,6), (3,7), (1000,5), (1000,6), (1000,7) },
    w: (a,b) ↦ a·b,
    M = { (1,5), (2,6), (3,7) }

Angenommen wir hätten zuerst das Matching {(1,5), (2,6), (3,7)} entdeckt. Dann ist       W(M) = w((1,5)) + w((2,6)) + w((3,7)) = 1·5 + 2·6 + 3 * 7 = 38.

Nun entferne ich die zwei Kanten (2,6) und (3,7) und füge stattdessen die Kante (1000,7) ein. Dann ist

W(M) = w((1,5)) + w((1000,7) = 1·5 + 1000 * 7 = 7001

wobei 7001 deutlich - deutlich - deutlich größer als 38 ist.

Wie zeige ich damit, dass es keinen beschränkten Approximationsfaktor gibt? Und später dann mit 3-Flip-Umgebung, dass der Faktor höchstens 2 ist?

---

Nun entferne ich die zwei Kanten (2,6) und (3,7) und füge stattdessen die Kante (1000,7) ein.

Um die Kante (1000,7) dem Matching hinzuzufügen, brauchst du (2,6) nicht zu entfernen. Es reicht, wenn du dazu (3,7) entfernst. Das heißt dann natürlich, dass das Matching { (1,5), (2,6), (1000,7) } mittels strikter lokaler Suche mit 2-Flip Umgebung um M gefunden werden kann.

Um a) zu beweisen, ist es wirklich wichtig, dass zwei Kanten entfernt werden müssen, damit eine neue Kante hinzugefügt werden darf. Erst dann ist ja sichergestellt, dass das Matching nicht mit 2-Flip Umgebung gefunden werden kann (zumindest nicht in einem Schritt).

Tipp: V₁ = {a,b}, V₂ = {c,d} reicht dazu aus. Du musst nur noch die Kanten und deren Gewichte festelegen und ein geeignetes M finden.

---

Ich bin gerade noch nicht "sichi wie Siegfried" was mit 'entfernen müssen' gemeint ist.

Angenommen wir haben

V1 = {1, 1000}

und V2 = {3,4}

Dann wäre ein Matching z.b. {(1,4), (1000, 3)} denn es hat den Wert 3005.

Entfernen wir jetzt die kanten (1,4) und (1000,2) und matchen stattdessen (1,3) und (4,1000) haben wir {(1,3), (1000,4), also 4003 - einen größeren Wert.

Aber woher weiß ich, dass ich bei {(1,4), (1000, 3)} die beiden Kanten wirklich entfernen muss? Wie kann ich mir sicher sein? Weil ich weiß das 4003 > 3005 ?

Und bei b) und c) dann einfach 3-Flips, dh. "Kante entfernen - einfügen - entfernen"? Oder "entfernen - einfügen - einfügen"?

---

Aber woher weiß ich, dass ich bei {(1,4), (1000, 3)} die beiden Kanten wirklich entfernen muss?

Natürlich musst du sie nicht entfernen. Du musst sie aber entfernen, wenn du (1000, 4) hinzufügen möchtest. Und du möchtest (1000, 4) hinzufügen, weil 4003 > 3005 ist.

Wenn du keine Kante entfernst, dann darfst du (1000, 4) nicht hinzufügen, weil

        {(1, 4), (1000, 3), (1000, 4)}

kein Matching ist.

Wenn du nur die Kante (1, 4) entfernst, dann darfst du (1000, 4) nicht hinzufügen, weil

        {(1000, 3), (1000, 4)}

kein Matching ist.

Wenn du nur die Kante (1000, 3) entfernst, dann darfst du (1000, 4) nicht hinzufügen, weil

         {(1, 4), (1000, 4)}

kein Matching ist.

Also musst du beide Kanten entfernen um (1000, 4) hinzufügen zu dürfen. Das heißt, dass kein Matching mit (1000, 4) in der 2-Flip Umgebung von {(1,4), (1000, 3)} ist.

In der 2-Flip Umgebung von {(1,4), (1000, 3)} sind ∅, {(1,4)} und {(1000, 3)}. Die haben aber alle ein geringeres Gewicht als {(1,4), (1000, 3)}, also terminiert die lokale Suche und liefert {(1,4), (1000, 3)}.

Problem ist noch, dass du das verallgemeinern musst, weil du im Moment einen Approximationsfaktor von 4003/3005 ≈ 1,7 hast.

Dazu brauchst du die Kante (1,3) nicht. Ausschlaggebend für das höhere Gewicht war ja nur die Kante (1000, 4). Außerdem schlage ich vor, von der Gewichtsfunktion w: (a,b) ↦ a·b abzusehen und stattdessen für jede einzelne Kante das Gewicht direkt festzulegen.

Zum Beispiel V₁ = {a,b}, V₂ = {c,d}, E = {(a,b), (a,d), (b,c)}, M = {(a,c), (b,d)} und w((a,c)) = 1, w((b,d)) = 1, w((b,c)) = ... .

Und bei b) und c) dann einfach 3-Flips, dh. "Kante entfernen - einfügen - entfernen"? Oder "entfernen - einfügen - einfügen"?

Ja. Wobei ich das Wort "einfach" streichen würde. Die a) war einfach. Bei b) und c) habe ich im Moment auch keine Idee.