Seminarvortrag: Randomisiertes Runden

Thomas Friedrich 27. Januar 1997

Seminar über Approximation Universität zu Köln

1 Einleitung

1.1 Methodik

Wir wollen uns hier mit der Methode des randomisierten Rundens beschäftigen, einer effizienten Technik zur Lösung von schwierigen Problemen, vor allem bei der kombinatorischen Optimierung. Meist formuliert man dazu das gegebene Optimierungsproblem als ein ganzzahliges lineares Programm. Dieses wird dann relaxiert (gelockert) auf ein nicht-ganzzahliges lineares Programm, für das polynomielle Algorithmen zur Lösung existieren, z. B. Innere-Punkt-Methoden. Durch Randomisierung wird dann aus der gewonnenen Lösung des LP’s möglichst effektiv die Ganzzahligkeit wiederhergestellt. Wir wollen das randomisierte Runden vor allem anwenden auf das integer multicommodity flow problem (ganzzahliges Mehrgüterfluß-Problem), außerdem auf Überdeckungs- und Packprobleme, sowie das ungerichtete Multicut-Problem. Dabei soll sich jeweils eine Analyse der Approximationsgüte anschließen. Eine zweite Möglichkeit, randomisiertes Runden anzuwenden, nämlich mittels semidefiniter Programmierung, werden wir hier nicht betrachten.

1.2 Einführendes Beispiel

Zur kurzen Einführung soll uns hier das Problem der Gitterapproximation (lattice-approximation problem, LAP) dienen. Hierbei geht es darum, zu einer gegebenen n × n-Matrix A, deren Einträge nur aus 0 und 1 bestehen, und einem gegebenen Spaltenvektor p, dessen n Einträge aus dem Intervall [0,1] stammen, einen Vektor q zu finden, dessen Komponenten nur 0 oder 1 sind, und der p bzgl. A möglichst genau approximiert, also ∥ A · (p − q) ∥_{∞} minimiert. Eine naive Lösungsmethode, die einem sofort einfällt, besteht darin, für alle Einträge p_{i} ≥ 0.5 das jeweilige q_{i} auf 1 zu setzen, sonst auf 0. Hierbei kann es allerdings vorkommen, daß für den resultierenden Vektor q gilt, daß ∥ A · (p − q) ∥_{∞} in etwa so groß ist wie ∥ A · q ∥_{∞}, die Approximation also nicht allzu gut ausfällt. Besonders bei einem Spezialfall des Gitterapproximations-Problems, dem setbalancing problem, wird dieses Vorgehen ad absurdum geführt: hier besteht nämlich der gegebene Vektor p nur aus Einträgen von 0.5; sämtliche Komponenten des Vektors q würden also geradeso auf 1 gesetzt. Dies ergibt aber verständlicherweise eine nicht sehr brauchbare Lösung. Setzt man hingegen die Komponente q_{i} mit der Wahrscheinlichkeit p_{i} auf 1 und sonst auf 0, ist zu erwarten, daß der resultierende Vektor q ”nahe“ bei p liegt. So kann man zeigen, daß für eine gegebene Instanz {A, p} des Gitterapproximations-Problems durch diesen Algorithmus eine Lösung q gefunden wird, für die ∥ A · (p − q) ∥_{∞}≤ \sqrt{4n ln n} mit einer Wahrscheinlichkeit von mindestens (1 − \frac{1}{n}) gilt. Wie man bereits sieht, spielt die Wahrscheinlichkeitstheorie beim randomisierten Runden eine große Rolle.

2 Stochastische Grundlagen

Definition: Bezeichne mit Pr[A] die Wahrscheinlichkeit, daß Ereignis A eintritt. Zwei Ereignisse A und B heißen unabhängig, falls gilt:

Pr[A ∧ B] = Pr[A] · Pr[B].

Eine Zufallsvariable X ist eine Funktion X : Ω → IR von der Menge der Ereignisse in die reellen Zahlen. Eine Bernoullische Zufallsvariable ist eine Zufallsvariable, die nur den Wert 0 oder 1 annimmt. Der Erwartungswert E[X] einer Zufallsvariablen X wird definiert als:

E[X] := ∑_{x∈Ω} x · p(x),

wobei p(x) := Pr[X = x], also die Wahrscheinlichkeit, daß X = x ist.

Lemma 1: (Linearität des Erwartungwertes) Für zwei Zufallsvariablen X, Y gilt:

E[X + Y] = E[X] + E[Y].

Beweis:

E[X] + E[Y] = ∑_{x∈Ω} xPr[X = x] + ∑_{x∈Ω} xPr[Y = x]

= ∑_{x∈Ω} x(Pr[X = x] + Pr[Y = x])

= E[X + Y].

q. e. d.

Bemerkung: Induktiv läßt sich Lemma 1 erweitern auf jede endliche Anzahl von Zufallsvariablen X_{1}, …, X_{n}, also:

E [∑_{i=1}^{n} X_{i}] = ∑_{i=1}^{n} E[X_{i}]

und sogar auf eine abzählbare Menge von Zufallsvariablen X_{1}, X_{2}, X_{3}, …:

E [∑_{i=1}^{∞} X_{i}] = ∑_{i=1}^{∞} E[X_{i}].

Definition: Das k-te Moment einer Zufallsvariablen X ist definiert als E[X^{k}].

Satz 2: Die Ungleichung für das k-te Moment lautet:

Pr[|X| ≥ λ] ≤ \frac{1}{λ^{k}} · E[|X|^{k}]

für eine Zufallsvariable X und λ > 0.

Beweis:

E[|X|^{k}] = ∑_{x∈Ω}(|x|^{k}p(x))

= ∑_{|x|<λ}(|x|^{k}p(x)) + ∑_{|x|≥λ}(|x|^{k}p(x))

≥ ∑_{|x|≥λ}(|x|^{k}p(x))

≥ λ^{k} ∑_{|x|≥λ} p(x)

= λ^{k}Pr[|X| ≥ λ],

also: Pr[|X| ≥ λ] ≤ \frac{1}{λ^{k}} ·E[|X|^{k}].

q. e. d.

Bemerkungen:

(i) Für k = 1 und λ·E[X] statt λ ergibt sich:

Pr[|X| ≥ λ · E[X]] ≤ \frac{1}{λ}.

Diese Ungleichung heißt Markows Ungleichung.

(ii) Für k = 2 und X−E[X] statt X, sowie λ · σ für λ, wobei σ := \sqrt{E[(X − E[X])^{2}]} die Standardabweichung ist, ergibt sich:

\begin{aligned}Pr[|X − E[X]| ≥ λ · σ] & ≤ \frac{1}{(λσ)^{2}} · E[(X − E[X])^{2}] \\ & = \frac{1}{λ^{2}σ^{2}} · σ^{2} = \frac{1}{λ^{2}} \end{aligned}

Diese Ungleichung heißt Tschebyschews Ungleichung.

(iii) Der Beweis von Satz 2 bleibt gültig, wenn man (…)^{k} durch eine beliebige monoton steigende Funktion g(x) auf [0, ∞[ ersetzt:

Pr[|X| ≥ λ] ≤ \frac{1}{g(λ)} · E[g(|X|)],

also z. B. g(x) := exp(tx). Man erhält:

Pr[|X| ≥ λ] ≤ exp(−tλ) · E[exp(tX)],

die Tschernoff-Ungleichung, wobei man t so wählen kann, daß die rechte Seite möglichst klein wird.

3 Multicommodity Flow I

Dieser Abschnitt soll den Schwerpunkt dieses Seminarvortrages darstellen.

3.1 Das Problem

Eine Variante des ganzzahligen Mehrgüterfluß-Problems, mit der wir uns nun beschäftigen wollen, läßt sich wie folgt formulieren: Gegeben sei ein gerichteter Graph G = (V, E) mit Quellen s_{i} ∈ V und Senken t_{i} ∈ V, i = 1, …, k. Die Aufgabe besteht nun darin, für jedes i einen Pfad P_{i} von s_{i} nach t_{i} durch G zu finden, so daß die Maximalbelastung der Kanten im Graphen so gering wie möglich gehalten wird. Die Belastung einer Kante ist dabei definiert als die Anzahl der Pfade, die über diese Kante laufen. Im allgemeinen ist dieses Problem NP-vollständig.

3.2 Formulierung als ganzzahliges lineares Optimierungsproblem

Bezeichne mit x_{i}(v, w) (wobei (v, w) ∈ E), ob der Pfad P_{i} von s_{i} nach t_{i} über (v, w) läuft (x_{i}(v, w) = 1), oder nicht (x_{i}(v, w) = 0). Dann sieht das zugehörige ganzzahlige lineare Optimierungsproblem wie folgt aus:

(1) minimiere W unter Berücksichtigung der Restriktionen:

(2) ∑_{w∈V} x_{i}(v, w) − ∑_{w∈V} x_{i}(w, v) = \begin{cases}1, & falls v = s_{i} \\ −1, & falls v = t_{i} \\ 0, & sonst \end{cases} i = 1, …, k

(3) ∑_{i=1}^{k} x_{i}(v, w) ≤ W für alle (v, w) ∈ E

(4) x_{i}(v, w) ∈ {0, 1} für alle (v, w) ∈ E und i = 1, …, k,

wobei (2) (evtl. nicht einfache) Pfade von s_{i} nach t_{i} erzwingt, da hier für jeden Knoten die Anzahl der Eingangskanten eines Pfades von der Zahl herausführender Kanten desselben Pfades abgezogen werden. Dies muß für den Startknoten 1 sein, für den Zielknoten -1 und für alle anderen 0. Ungleichung (3) hält die Belastung jeder Kante unter der Schwelle W, und (4) garantiert, daß die x_{i} nur die beiden zulässigen Werte 0 und 1 annehmen können.

(1) minimiert dann über die Maximalbelastung W einer Kante im Graphen.

3.3 Relaxierung auf LP

Wir können das ganzzahlige lineare Optimierungsproblem in ein lineares Programm (LP) überführen, indem wir die Bedingung (4): x_{i}(v, w) ∈ {0, 1} lockern auf x_{i}(v, w) ≥ 0. Da nun aber der Raum der zulässigen Lösungen ungemein größer ist, werden die optimalen Lösungen W^{∗} für das ganzzahlige Problem und W_{LP} für das relaxierte Problem im allgemeinen nicht übereinstimmen. Jedoch läßt sich nun das LP mittels geeigneter Algorithmen in polynomieller Zeit lösen. Die erhaltene Optimallösung wird i. a. nicht ganzzahlig sein, was auch nicht zu erwarten war.

3.4 Flow Decomposition

Die gebrochene Lösung kann in Pfade zerlegt werden mit Hilfe von flow decomposition (Flußzerlegung), einer Standardtechnik bei Flüssen im Netzwerk: Sei dazu x ≥ 0 und

∑_{w∈V} x(v, w) − ∑_{w∈V} x(w, v) = \begin{cases}a, & falls v = s_{i} \\ −a, & falls v = t_{i} \\ 0, & sonst \end{cases} i = 1, …, k

(Beachte die Ähnlichkeit zu (2) mit a = 1.) Dann kann man für festes i ∈ {1, …, k} Pfade P_{1}, …, P_{l} von s_{i} nach t_{i} finden mit α_{1}, …, α_{l} ∈ IR^{+}, so daß

∑_{j=1}^{l} α_{j} = a,
∑_{j:(v,w)∈P_{j}} α_{j} ≤ x(v, w).

Dies sei hier ohne Beweis angegeben.

3.5 Der Algorithmus nach Raghavan und Thompson

Der folgende Algorithmus, der zur Lösung des Problems randomisiertes Runden verwendet, geht auf Raghavan und Thompson zurück.

Algorithmus (RT):

1. Löse das relaxierte LP, erhalte dabei die Lösung W_{LP} .

2. Zerlege die gebrochene Lösung mittels flow decomposition in Pfade P_{ij}, i = 1, …, k, j = 1, …, j_{i}, wobei P_{ij} ein Pfad von s_{i} nach t_{i} durch G bezeichnet. Man erhält die α_{ij} ∈ IR^{+} mit ∑_{j=1}^{l_{i}} α_{ij} = 1, so daß gilt:

∑_{i=1}^{k} ∑_{j:(v,w)∈P_{ij}} α_{ij} ≤ W_{LP} .

3. Randomisierungsschritt: Für jedes i ∈ {1, …, k} werfen wir einen j_{i}- seitigen ”Würfel“, bei dem mit Wahrscheinlichkeit α_{ij} die ”Seite“ j erscheint. Sei f das Ergebnis dieses Wurfes; wähle dann den Pfad P_{if} als den Pfad von s_{i} nach t_{i}.

3.6 Analyse

Die folgende Analyse des Algorithmus soll zeigen, daß wir mit hoher Wahrscheinlichkeit eine geringe Kantenbelastung im Graphen erhalten.

Lemma 3: (Tschernoff-Schranke) Seien X_{i}, i = 1, …, k, unabhängige Bernoulli-Zufallsvariablen mit Wahrscheinlichkeiten Pr[X_{i} = 1] = p_{i} (und damit Pr[X_{i} = 0] = (1 − p_{i})) für alle i. Dann gilt für alle α > 0 und alle t > 0:

Pr [∑_{i=1}^{k} X_{i} ≥ t] ≤ exp(−αt) ∏_{i=1}^{k} E[exp(αX_{i})]

= exp(−αt) ∏_{i=1}^{k}(p_{i} exp(α) + (1 − p_{i})).

Beweis:

Pr [∑_{i=1}^{k} X_{i} ≥ t] ≤ exp(−αt) · E [exp (α ∑_{i=1}^{k} X_{i})]

= exp(−αt) · E [∏_{i=1}^{k} exp(αX_{i})]

= exp(−αt) · ∏_{i=1}^{k} E[exp(αX_{i})].

q. e. d.

Korollar 4: Seien X_{i}, i = 1, …, k, unabhängige Bernoulli-Zufallsvariablen, und sei M := E[∑_{i=1}^{k} X_{i}] = ∑_{i=1}^{k} p_{i}. Dann gilt für alle β > 0:

\begin{aligned}Pr [∑_{i=1}^{k} X_{i} ≥ (1 + β) · M] & ≤ (1 + β)^{−(1+β)·M} ∏_{i=1}^{k} E[(1 + β)^{X_{i}}] \\ & ≤ (\frac{exp(β)}{(1 + β)^{(1+β)}} )^{M} . \end{aligned}

Die zweite Ungleichung folgt aus:

E[(1 + β)^{X_{i}}] = p_{i}(1 + β) + (1 − p_{i}) = 1 + βp_{i} ≤ exp(βp_{i}).

Theorem 5: Sei ε > 0; ferner sei W^{∗} die Optimallösung des obigen multicommodity flow-Problems mit W^{∗} = Ω(log n), wobei n = |V |. Dann erzeugt der Algorithmus (RT) mit Wahrscheinlichkeit (1 − ε) eine Lösung für die Maximalbelastung einer Kante im Graphen

W ≤ W^{∗} + c · \sqrt{W^{∗} ln n},

wobei c und die Konstante aus der Ω-Notation von ε abhängen.

Beweis: Sei (v, w) ∈ E beliebig, aber fest. Die Kante (v, w) wird vom Produkt i mit der Wahrscheinlichkeit

p_{i} = ∑_{j:(v,w)∈P_{ij}} α_{ij}

benutzt. Sei nun X_{i} eine Bernoulli-Zufallsvariable, die angibt, ob (v, w) von P_{i} benutzt wird (X_{i} = 1), oder nicht (X_{i} = 0). Dann ist W (v, w) := ∑_{i=1}^{k} X_{i} die Belastung der Kante (v, w). Damit ist

E[W (v, w)] = ∑_{i=1}^{k} p_{i} = ∑_{i=1}^{k} ∑_{j:(v,w)∈P_{ij}} α_{ij} ≤ W_{LP} ≤ W^{∗}.

Mit Lemma 3 (Tschernoff-Schranke) und Korollar 4 folgt:

Pr[W (v, w) ≥ (1 + β)W^{∗}] ≤ (\frac{exp(β)}{(1 + β)^{(1+β)}} )^{W^{∗}}

= exp((β − (1 + β) ln(1 + β))W^{∗}).

Sei jetzt β ≤ 1; dann gilt:

\frac{exp(β)}{(1 + β)^{(1+β)}} = exp(β − (1 + β) ln(1 + β)) ≤ exp(\frac{−β^{2}}{3} ).

Somit ist für β := \sqrt{\frac{3 ln \frac{n^{2}}{ε}}{W^{∗}}}:

Pr[W (v, w) ≥ (1 + β) · W^{∗}] ≤ \frac{ε}{n^{2}} .

(Die Annahme β ≤ 1 trifft zu, wenn W^{∗} ≥ 6 ln n − 3 ln ε ist.) Mit obiger Wahl von β ist also

\begin{aligned}(1 + β) · W^{∗} & = W^{∗} + βW^{∗} = W^{∗} + \sqrt{\frac{3 ln \frac{n^{2}}{ε}}{W^{∗}}} · W^{∗} \\ & = W^{∗} + \sqrt{\frac{W^{∗2} · 3 ln \frac{n^{2}}{ε}}{W^{∗}}} = W^{∗} + \sqrt{3W^{∗} ln \frac{n^{2}}{ε}} . \end{aligned}

Jetzt gilt für die Wahrscheinlichkeit, daß die Maximalbelastung größer ist als (1 + β) · W^{∗} :

\begin{aligned}Pr[ max_{(v,w)∈E} W (v, w) > (1 + β) · W^{∗}] & ≤ ∑_{(v,w)∈E} Pr[W (v, w) ≥ (1 + β) · W^{∗}] \\ & ≤ |E| · \frac{ε}{n^{2}} ≤ ε, \end{aligned}

was wir zeigen wollten.

q. e. d.

3.7 Derandomisierung

Die Derandomisierung erfolgt mit Mitteln der bedingten Wahrscheinlichkeiten. Außerdem fließt noch ein ”kleiner Trick“ mit ein. Wir stellen den Wahrscheinlichkeitsraum als Entscheidungsbaum dar. Wir starten an der Wurzel, an der wir noch keine Entscheidung getroffen haben. Während wir uns nun den Baum hinabhangeln, legen wir nacheinander fest, welche Pfade von den einzelnen Gütern benutzt werden sollen. Dabei entscheiden wir zunächst für Produkt 1, dann für Produkt 2, usw. An jedem Knoten des Baumes stellen also die ausgehenden Kanten die möglichen Entscheidungen über die Wahl des Pfades für das nächste Produkt dar. Somit hat die Wurzel j_{1} Söhne, da wir ja j_{1} verschiedene Pfade für Produkt 1 zur Auswahl haben. Jeder dieser Söhne hat wiederum j_{2} Söhne, zur Wahl des Pfades für Produkt 2, usw. Irgendwann erreichen wir die k-te Ebene (ganz unten). Hier befinden sich die Blätter des Baumes, die zusammen alle möglichen Entscheidungen für die k Produkte repräsentieren. Seien wir beim Hinabsteigen des Baumes nach i bereits getroffenen Entscheidungen l_{1}, …, l_{i} für die Produkte 1, …, i bei einem Knoten in Ebene i angekommen (wobei die Wurzel in Ebene 0 liegt). Wir definieren jetzt:

g(l_{1}, …, l_{i}) := Pr[ max_{(v,w)∈E} W (v, w) ≥ (1 + β) · W^{∗}|
l_{1} für Produkt 1, …, l_{i} für Produkt i].

Wir wollen nun einen Pfad für das (i + 1)te Produkt festlegen. Es gilt:

g(l_{1}, …, l_{i}) = ∑_{j=1}^{j_{i}} α_{ij} · g(l_{1}, …, l_{i}, j) ≥ min_{j} g(l_{1}, …, l_{i}, j).

Könnte man jetzt g effizient berechnen, könnten wir, ausgehend von g(∅) und bei jeweiliger Wahl des Minimums auf jeder Ebene des Entscheidungsbaumes, eine Folge g(∅) ≥ g(l_{1}) ≥ g(l_{1}, l_{2}) ≥ … ≥ g(l_{1}, …, l_{k}) konstruieren. Unglücklicherweise geht dies aber nicht. Hier kommt der ”kleine Trick“ ins Spiel: Anstelle der exakten Berechnung von g fragen wir einen ”pessimistischen Einschätzer“, wie groß die Wahrscheinlichkeit für einen Fehler ist. Wegen Korollar 4 und aus der (RT)-Analyse wissen wir:

Pr[ max_{(v,w)∈E} W (v, w) ≥ (1+β)·W^{∗}] ≤ (1+β)^{−(1+β)·W^{∗}} ∑_{(v,w)∈E} E [∏_{i=1}^{k} exp(βX_{i}^{(v,w)})] ,

wobei X_{i}^{(v,w)} von der Kante (v, w) abhängt. Sei h(l_{i}, …, l_{i}) die Summe auf der rechten Seite dieser Ungleichung; insgesamt ergibt sich dann:

1. h(l_{1}, …, l_{i}) kann leicht berechnet werden

2. g(l_{1}, …, l_{i}) ≤ h(l_{1}, …, l_{i})

3. h(l_{1}, …, l_{i}) ≥ min_{j} h(l_{1}, …, l_{i−1}, j).

Wenn wir also in der letzten Ungleichung in jeder Ebene das Minimum wählen, ergibt sich die Folge

1 > ε ≥ h(∅) ≥ h(l_{1}) ≥ h(l_{1}, l_{2}) ≥ … ≥ h(l_{1}, …, l_{k}).

Weil g(l_{1}, …, l_{k}) ∈ {0, 1} sein muß, kann sich durch die Wahl der Pfade in diesem deterministischen Algorithmus nur eine maximale Belastung von höchstens (1 + β) · W^{∗} ergeben.

4 Multicommodity Flow II

Hier wollen wir jetzt das ganzzahlige Mehrgüterfluß-Problem in seiner klassischen Form betrachten.

4.1 Problem

Die Aufgabe ist in diesem Fall quasi umgekehrt: zu einem gerichteten Graphen G = (V, E), ist zu jeder Kante e ∈ E eine maximale Kapazität c(e) gegeben. Außer den Quellen s_{i} ∈ V und den Senken t_{i} ∈ V, i = 1, …, k, besteht eine Instanz noch aus ganzzahligen Nachfragen d_{i} nach Produkt i. Gesucht sind ganzzahlige Flüsse f_{i}(e) über die Kanten von G, so daß mindestens d_{i} Einheiten von Produkt i von s_{i} nach t_{i} fließen. Bei der Lösung des Problems sind also folgende Restriktionen zu beachten:

(1) Sämtliche Flüsse f_{i}(e) über jede Kante e sollen ganzzahlig sein: f_{i}(e) ∈ {0, 1} für alle e ∈ E, i = 1, …, k.

(2) Für jedes Produkt sollen die in einem Knoten eingehenden und ausgehenden Flüsse gleich sein (außer natürlich Start- und Endknoten).

(3) Die Kapazität einer Kante darf nicht überschritten werden: ∑_{i=1}^{k} f_{i}(e) ≤ c(e) für alle e ∈ E.

(4) Die Nachfragen d_{i} sollen erfüllt werden:

∑_{e∈A_{i}} f_{i}(e) ≥ d_{i},

wobei A_{i} die Menge des Produktes i angibt, die s_{i} verläßt.

Es kann passieren, daß sich dieses Problem nicht lösen läßt, nämlich dann, wenn die Kapazitäten der Kanten nicht ausreichen, um die Nachfragen zu decken.

Wir beschäftigen uns hier mit einer Optimierungsvariante: Gegeben sei eine Instanz (s_{i}, t_{i}, d_{i}), i = 1, …, k, dieses ganzzahligen Mehrgüterfluß-Problems. Wir wollen nun den Gesamtfluß

∑_{i=1}^{k} ∑_{e∈A_{i}} f_{i}(e)

maximieren. Dabei beschränken wir uns auf den Fall, daß alle d_{i} = 1 sind. Dieselbe Technik ist aber mit geringen Änderungen auch auf den allgemeinen Fall d_{i} ≥ 1 anwendbar. Nun ergibt sich in Verbindung mit (1) - (4) ein ganzzahliges lineares Optimierungsproblem. Relaxiert man (1): f_{i}(e) ∈ {0, 1} auf f_{i}(e) ∈ [0, 1] für alle e ∈ E, i = 1, …, k, könnte man das entstandene LP wieder effizient lösen. Stattdessen wollen wir ein leicht modifiziertes LP lösen; wir setzen dazu die Kapazität jeder Kante auf (1 − ε) · c(e), für eine positive Konstante ε < \frac{\sqrt{5}−1}{2}, sonst lassen wir alles gleich. Die gebrochene Lösung dieses linearen Programms bezeichnen wir mit f̂_{i}(e), der entstehende Gesamtfluß sei

F̂ = ∑_{i=1}^{k} ∑_{e∈A_{i}} f_{i}(e).

Ferner bezeichne F die Optimallösung des ganzzahligen Problems. Dann ist F̂ ≥ (1−ε)F und der Fluß über jede Kante bei der nicht-ganzzahligen Lösung ist höchstens das (1 − ε)-fache ihrer Kapazität.

4.2 Randomisierung

Wir wenden jetzt das randomisierte Runden wie folgt an: Für jedes Produkt i gehen wir zufällig von s_{i} nach t_{i} durch den Graphen, indem wir erst einmal eine Münze mit ”Kopf“ und ”Zahl“ werfen, wobei die Wahrscheinlichkeit, daß ”Kopf“ erscheint, gleich ∑_{e∈A_{i}} f̂_{i}(e) ≤ 1 sei. Wenn die Münze ”Zahl“ zeigt, setzen wir hier den Fluß für Produkt i auf 0. Zeigt die Münze aber ”Kopf“, gehen wir weiter durch den Graphen. Seien wir so bei Knoten v angekommen; wir wählen den weiteren Weg über Kante a ∈ A(v) mit der Wahrscheinlichkeit \frac{f̂_{(}a)}{∑_{e∈A(v)} f̂_{i}(e)}, wobei A(v) die Menge der v verlassenden Kanten sei. Der Weg durch den Graphen für Produkt i endet mit dem Erreichen der Senke t_{i}, was nach spätestens (n − 1) Schritten der Fall ist, da die Menge der Kanten, deren Durchfluß größer als 0 ist, o. B. d. A. als kreisfrei angenommen werden kann.

Lemma 6: Seien X_{1}, …, X_{n} unabhängige Bernoulli-Zufallsvariablen mit Pr[X_{i} = 1] = p_{i} und Pr[X_{i} = 0] = (1 − p_{i}) für alle i = 1, …, n. Sei ferner Y = ∑_{i=1}^{n} X_{i}, also E[Y] = ∑_{i=1}^{n} p_{i}. Dann gilt für alle β ∈ [0, 1] :

Pr[|Y | − E[Y]| ≥ βE[Y]] ≤ 2 exp(−0.38β^{2}E[Y]).

Diese Behauptung folgt aus Bemerkung (iii) zu Satz 2.

Theorem 7: Sei eine Instanz des Mehrgüterfluß-Problems gegeben, bei der die Kapazität jeder Kante mindestens 5.2 ln 4m beträgt, wobei m := |E|. Sei ferner eine positive Konstante ε < \frac{\sqrt{5}−1}{2} gegeben. Dann liefert obiger Algorithmus eine ganzzahlige Lösung mit einem Gesamtfluß von mindestens (1 − ε)^{2}F mit einer Wahrscheinlichkeit von mindestens (1 − \frac{1}{m} − 2 exp(−0.38ε^{2}F)), wobei F der Gesamtfluß in der ganzzahligen Optimallösung ist.

Beweis: Der Algorithmus liefert immer nur eine ganzzahlige Lösung. Also kann nur einer der folgenden beiden Fälle eintreten:

1. Die Kapazität einer Kante ist überschritten. Die Wahrscheinlichkeit, daß dieser Fall eintritt, beträgt höchstens \frac{1}{m^{2}} . Die Wahrscheinlichkeit über alle Kanten summiert ist m · \frac{1}{m^{2}} = \frac{1}{m}.

2. Der Gesamtfluß ist kleiner als (1 − ε)^{2}F. Wir haben bereits festgestellt, daß der Gesamtfluß mindestens (1 − ε)F beträgt. Die Anwendung von Lemma 6 mit β = ε liefert die Schranke 2 exp(−0.38ε^{2}F) für die Wahrscheinlichkeit, daß der Fluß kleiner als (1−ε)^{2}F ist. Insgesamt ergibt sich also die Wahrscheinlichkeit 1−(\frac{1}{m})−(2 exp(−0.38ε^{2}F), was zu zeigen war.

q. e. d.

Bemerkung: Die Fehlerwahrscheinlichkeit läßt sich durch wiederholtes (voneinander unabhängiges) Anwenden des randomisierten Rundens vermindern. Bei den meisten Anwendungen ist nämlich das Finden der Optimallösung für das nicht-ganzzahlige LP der eigentliche Rechenaufwand. Der Schritt des randomisierten Rundens ist schnell durchführbar und kann deshalb auch leicht mehrmals wiederholt werden.

5 Covering & Packing

5.1 Allgemeine Problemstellung

Seien A eine m × n-Matrix über ZZ_{+}, b ∈ ZZ_{+}^{m}, und seien x, w ∈ ZZ_{+}^{n}. Dann heißt das Problem

min{w^{T} x|Ax ≥ b}

Überdeckungsproblem (covering problem) und das Problem

max{w^{T} x|Ax ≤ b}

Packproblem (packing problem). Im Sinne der linearen Programmierung sind Überdeckungs- und Packprobleme also zueinander dual. Außerdem sind beide Problemsorten i. a. NPvollständig.

5.2 Beispiel: Set Cover

In diesem Abschnitt wollen wir randomisiertes Runden auf einen Spezialfall der Packprobleme anwenden, nämlich auf das Problem der Mengenüberdeckung (set cover problem, SC). Sei dazu V = {v_{1}, …, v_{n}} eine Menge von Elementen, S = {S_{1}, …, S_{m}} eine Familie von Teilmengen von V. Es gibt jetzt zwei verschiedene Problemstellungen für das set cover problem. Bei der ersten Formulierung wird jedem Element v_{i} ∈ V ein Gewicht w(v_{i}) zugeordnet. Jetzt soll eine Teilmenge V′ von V mit minimalem Gewicht gefunden werden, so daß aus jeder Menge aus S mindestens ein Element in V′ enthalten ist. Das Gewicht einer Menge ist dabei die Summe der Gewichte der in ihr enthaltenen Elemente. Bei der zweiten Version wird jeder Menge S_{j} ∈ S ein Gewicht w(S_{j}) zugeordnet. Es sind nun Mengen S_{k_{1}}, …, S_{k_{l}} ∈ S mit minimalem Gesamtgewicht gesucht, deren Vereinigung ganz V überdeckt. Es ist leicht einzusehen, daß diese beiden Probleme zueinander äquivalent sind. Wir beschäftigen uns daher nur mit dem ersten Fall, der auch als hitting set problem bekannt ist. Wir formulieren zunächst wieder ein ganzzahliges Optimierungsproblem. Dabei bezeichne x_{i}, i = 1, …, n, ob Element v_{i} zur Überdeckung benutzt wird (x_{i} = 1), oder nicht (x_{i} = 0).

Wir erhalten:

Minimiere ∑_{i=1}^{n} w_{i} · x_{i},
so daß ∑_{i:v_{i}∈S_{j}} x_{i} ≥ 1 für alle S_{j} ∈ S
und  x_{i} ∈ {0, 1}  i = 1, …, n.

Wir relaxieren dieses ganzzahlige Problem wieder in ein nicht-ganzzahliges LP, indem wir nicht mehr x_{i} ∈ {0, 1}, sondern nur noch x_{i} ∈ [0, 1] fordern. Sei x̂_{i} der Wert der Variablen x_{i} nach der Lösung des relaxierten LP’s. Jetzt wollen wir ja wissen, welche der v_{i} wir für eine Überdeckung brauchen. Dafür wenden wir nun wieder randomisiertes Runden an, indem wir jede Variable x_{i} mit der Wahrscheinlichkeit x̂_{i} auf 1 setzen. Der Erwartungswert für das Gesamtgewicht des so entstandenen V′ ist ∑_{i=1}^{n} w_{i}x̂_{i}. Wie groß ist jetzt die Wahrscheinlichkeit, daß wir eine Menge S_{j} auch wirklich überdeckt haben ? Dazu enthalte S_{j} die Elemente v_{1}, …, v_{k}. Nach der ersten Bedingung gilt: ∑_{i=1}^{k} x̂_{j} ≥ 1. Somit ist die Wahrscheinlichkeit, daß die Menge S_{j} überdeckt ist:

1 − ∏_{i=1}^{k}(1 − x̂_{i}) ≥ 1 − (1 − \frac{1}{k})^{k} ≥ 1 − \frac{1}{e},

wobei e die Eulersche Zahl 2.71828... ist. Die Wahrscheinlichkeit, S_{j} überdeckt zu haben, ist also mindestens so groß wie die Konstante (1− \frac{1}{e}) ≈ 0.632. Um die Wahrscheinlichkeit, alle Mengen aus S überdeckt zu haben, zu erhöhen, wenden wir das randomisierte Runden erneut auf diejenigen x_{i} an, die nicht auf 1 gesetzt wurden. Wenn wir so z. B. t = O(log m)-mal das randomisierte Runden anwenden, ist die Wahrscheinlichkeit, daß eine Menge S_{j} nicht überdeckt wurde, höchstens \frac{1}{2^{m}}. Somit ist nach den t Anwendungen des Algorithmus die Wahrscheinlichkeit, daß nicht alle Mengen aus S getroffen wurden, höchstens \frac{1}{2} und der Erwartungswert des Gesamtgewichtes von V′ höchstens t · ∑_{i=1}^{k} w_{i}x̂_{i},.

Aus diesen Überlegungen ergibt sich insgesamt:

Theorem 8: Zu jeder Instanz {V, S} des set cover problem kann mit randomisiertem Runden eine O(log m)-approximative Überdeckung mit einer Wahrscheinlichkeit von mindestens \frac{1}{2} gefunden werden.

Bemerkung: Die Schranke aus Theorem 8 ist noch nicht optimal, sie kann noch verbessert werden; jedoch kann man zeigen, daß sie höchstens 1+ln Δ sein kann, wobei Δ die maximale Anzahl von Mengen aus S ist, die mit einem einzigen Element aus V überdeckt werden können.

6 Undirected Multicut

6.1 Problemstellung

Eine Instanz des ungerichteten Multicut-Problems besteht aus einem ungerichteten Graphen G = (V, E), einer auf den Kanten definierten Gewichtsfunktion c : E → IR^{+}, sowie Knotenpaaren (s_{i}, t_{i}), i = 1, …, k. Die Aufgabe lautet: Finde eine Menge von Kanten, so daß nach dem Entfernen dieser Kanten aus dem Graphen jede Quelle s_{i} von der zugehörigen Senke t_{i} getrennt ist, also nicht in derselben Zusammenhangskomponente liegt. Dabei soll die Summe über die Gewichte der entfernten Kanten minimal sein. Auch dieses Problem ist NP-vollständig.

6.2 Zurückführung auf Set Cover

Wir können das Problem in kanonischer Weise in das set cover problem überführen. Dazu entsprechen die Kanten im Graphen den (gewichteten) Elementen aus dem SC-Problem, und jeder Pfad zwischen der Quelle s_{i} und der Senke t_{i} definiere eine Teilmenge aus S. Eine Überdeckung der Menge S durch Kanten aus G bedeutet, daß aus jedem Pfad von s_{i} nach t_{i} mindestens eine Kante entfernt wird. Die minimale Überdeckung beim set cover problem entspricht dann dem minimalen Schnitt durch G, so daß jeweils s_{i} und t_{i} getrennt werden. Bei diesem Vorgehen wird allerdings nur ein sehr schlechter Approximationsfaktor erreicht, der in der Größenordnung von Ω(|V |) liegen kann. Deshalb formulieren wir das ungerichtete Multicut-Problem auf eine andere Weise in das set cover problem um. Das folgende Verfahren stammt von Bertsimas und Vohra: Seien in F alle diejenigen Teilmengen von V mit der Eigenschaft, daß für jedes S ∈ F höchstens einer der beiden Knoten s_{i} und t_{i}, i = 1, …, k, in S enthalten ist. Wir bezeichnen mit δ(S) die Menge der Kanten, die genau einen Endpunkt in S haben. Ferner sei c(A) definiert als die Summe der Gewichte in Menge A. a_{iS} gebe an, ob sich die Quelle s_{i} in S befindet (a_{iS} = 1), oder nicht (a_{iS} = 0). Analog sei b_{iS} für die Senken definiert. Die Variable x(S) sei 1, wenn die Menge S für die Überdeckung benötigt wird, ansonsten 0. Dies ergibt folgendes ganzzahlige lineare Programm:

Minimiere \frac{1}{2} ∑_{S∈F} c(δ(S)) · x(S),
so daß ∑_{S∈F} a_{iS} · x(S) ≥ 1 für alle s_{i}, i = 1, …, k
∑_{S∈F} b_{iS} · x(S) ≥ 1 für alle t_{i}, i = 1, …, k
x(S) ∈ {0, 1} für alle S ∈ F.

Hier wird also versucht, sämtliche Quellen und Senken im Graphen durch Mengen aus F zu überdecken. Somit induziert eine Lösung dieses ganzzahligen LP’s einen zulässigen Multicut in G, und umgekehrt.

Jetzt relaxieren wir wieder die letzte Bedingung x(S) ∈ {0, 1} auf x(S) ∈ [0, 1], und lösen das nicht-ganzzahlige LP, was ja in polynomieller Zeit möglich ist. An dieser Stelle wenden wir auf die so erhaltene Lösung den Randomisierungsschritt des set cover problem (vgl. Kapitel 5) an, um eine Lösung für den Multicut zu erhalten. Weil die Anzahl der zu überdeckenden Elemente 2k ist, ergibt sich wie für das set cover problem ein Approximationsfaktor von O(log k). Somit erzielen wir mit randomisiertem Runden ein vergleichbar gutes Ergebnis wie der Algorithmus von Garg, Vazirani und Yannakakis, von dem wir schon vorher im Seminar gehört haben, und der deterministisch arbeitet.

Inhaltsverzeichnis

1 Einleitung 1 1.1 Methodik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Einführendes Beispiel . . . . . . . . . . . . . . . . . . . . . . . 1

2 Stochastische Grundlagen 2

3 Multicommodity Flow I 5 3.1 Das Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.2 Formulierung als ganzzahliges lineares Optimierungsproblem . 5 3.3 Relaxierung auf LP . . . . . . . . . . . . . . . . . . . . . . . . 6 3.4 Flow Decomposition . . . . . . . . . . . . . . . . . . . . . . . 6 3.5 Der Algorithmus nach Raghavan und Thompson . . . . . . . . 6 3.6 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.7 Derandomisierung . . . . . . . . . . . . . . . . . . . . . . . . . 9

4 Multicommodity Flow II 11 4.1 Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.2 Randomisierung . . . . . . . . . . . . . . . . . . . . . . . . . . 12

5 Covering & Packing 14 5.1 Allgemeine Problemstellung . . . . . . . . . . . . . . . . . . . 14 5.2 Beispiel: Set Cover . . . . . . . . . . . . . . . . . . . . . . . . 14

6 Undirected Multicut 16 6.1 Problemstellung . . . . . . . . . . . . . . . . . . . . . . . . . . 16 6.2 Zurückführung auf Set Cover . . . . . . . . . . . . . . . . . . . 16

erstellt mit L^{A}TEX2ε.