Gewichtetes Matching-Problem

Problemstellung: gewichtetes Matching-Problem

Gegeben ein Ungerichteter Graph $G=(V,E)$ und eine Kostenfunktion $c:E\to\mathbb R$. Finde das Perfekt Matching $M$ von $G$, das die totalen Kosten $\sum_{e\in M}c(e)$ minimiert.

Lösung für Bipartiter Graph

Gegeben ein vollständiger bipartiter Graph $G=(V,E)$.

Durch die Bipartitheit lassen sich die Knoten in zwei Mengen $A$ und $B$ zerlegen.

Falls $G$ zu beginn nicht vollständig ist, kann er in einen vollständigen Graphen transformiert werden in dem die fehlenden Kanten mit unendlich großem Gewicht hinzugefügt werden.

Somit ist die Kostenfunktion für eine Kante $\{i,j\}$ gegeben durch $c_{i,j}\in\mathbb R\cup\{\infty\}$ mit $i\in A$ und $j\in B$.

Das gewichtetes Matching-Problem können wir nun als ILP ausdrücken:

$$\begin{align}\min&\sum_{i\in A,j\in B} c_{i,j}x_{i,j} \\\mathrm{s.t.}&\sum_{i\in A}x_{i,j} = 1 &\forall i\in A\\&\sum_{j\in B} x_{i,j} = 1 &\forall j\in B\\&x_{i,j} \in \{0,1\} &\forall i\in A,j\in B\\\end{align}$$

Nun wird die Bedingung das die Variablen $x_{i,j}$ ganzen Zahlen sein müssen durch ein Intervall ersetzt. Wir erhalten folgende LP:

Daraus folgt das bitpartite perfekte matching Polytop

$$P=\left\{x\mid\sum_{i\in A}x_{i,j} = 1 \forall i\in A, \sum_{j\in B} x_{i,j} = 1 \forall j\in B, x_{i,j} \in [0,1] \forall i\in A,j\in B\right\}$$

Da jedes Lösung von IP auch eine erlaubte Lösung von LP ist, wird der Zielfunktionswert von IP immer durch den Zielfunktionswert von LP von unten Beschränkt.

Satz

Jeder Extremalpunkt von $P$ ist ein inegraler Vektor (besteht nur aus 1 und/oder 0) und ist daher auch der Inzidenzvektor eines Perfekt Matching.

Sei $u_i$ für alle $i\in A$ und $v_j$ für alle $j\in B$ so, dass $u_i+v_j \leq c_{i,j}$ für alle $i\in A,j\in B$. Dann muss für jedes Perfekt Matching $M$ gelten, dass

$$\begin{align}\sum_{\{i,j\}\in M,i\in A,j\in B} c_{i,j}&\geq\sum_{\{i,j\}\in M,i\in A,j\in B} (u_i+v_j)&\Huge|\normalsize\text{Def. $u_i,v_j$}\\&=\sum_{\{i,j\}\in M,i\in A,j\in B}u_i+\sum_{\{i,j\}\in M,i\in A,j\in B}v_j&\Huge|\normalsize\text{Eig. $\Sigma$}\\&=\sum_{i\in A}u_i+\sum_{j\in B}v_j&\Huge|\normalsize\text{Eig. $M$ (pm)}\\\end{align}$$

Hier wird $u$ und $v$ zusammen als duale Lösung genannt.

Somit ist $\sum_{i\in A}u_i+\sum_{j\in B}v_j$ eine untere Schranke für die Kosten eines minimum Perfekt Matching. Durch Maximierung erhalten wir folgende LP $D$

$$\begin{align}\max&\sum_{i\in A}u_i+\sum_{j\in B}v_j\\\mathrm{s.t.}\;& u_i+ v_j \leq c_{i,j} &\forall i\in A, j\in B\\&u_i,v_j \in \mathbb R&\forall i\in A,j\in B\\\end{align}$$

Folgende Gleichung zeigt das die Lösung von $D$ eine untere Schranke für alle Punkte $x$ aus $P$.

$$\begin{align}\sum_{i\in A}\sum_{j\in B} c_{i,j}x_{i,j}&\geq\sum_{i\in A}\sum_{j\in B} (u_i+v_j)x_{i,j} &\Huge|\normalsize\text{Def. $u_i,v_j$}\\&=\left(\sum_{i\in A} u_i\sum_{j\in B}x_{i,j}\right)+\left(\sum_{j\in B} u_j\sum_{i\in A}x_{i,j}\right)&\Huge|\normalsize\text{Eig. $\Sigma$}\\&=\sum_{i\in A}u_i+\sum_{j\in B}v_j&\Huge|\normalsize\text{Def. $x$}\\\end{align}$$

Zusammenfassend ergibt sich folgende Bild:

$$\min_{\textrm{perf. match. }M}\sum_{(i,j)\in M} c_{i,j}\geq\min_{x\in P}\sum_{(i,j)\in M} c_{i,j}x_{i,j}\geq\max_{(u,v)\in D}\sum_{i\in A}u_i+\sum_{j\in B}v_j$$

Das heißt: wenn wir ein perfektes Matching $M$ und eine Lösung $u,v$ für $D$ finden so, dass aus aus den Ungleichungen Gleichheiten werden, dann ist $M$ ein optimales perfekte matching. Die Ungleichungen werden zu Gleichungen wenn $w_{i,j} := c_{i,j}-u_i-v_j = 0$ für alle Kanten $\{i,j\}\in M$.

Nun können wir einen Algorithmus für das Problem formulieren.

Algorithmus

Folgender Algorithmus löst das Problem.

Beginne mit einer (zufälligen) dualen Lösung $u,v$ für $D$. So z.B. $\forall i\in A : u_i=0$ und $\forall j\in B:v_j = \min_{i\in A}c_{i,j}$.
Sei $G$ der Teilgraph der sich aus den Kanten $E=\left\{\{i,j\}\mid i\in A,j\in B,w_{i,j}=0\right\}$
Benutze diesen Algorithmus um das Maximum Matching $M$ von $G$ zu ermitteln.
Falls $M$ perfekt ist, dann muss $M$ optimal sein. Also gebe $M$ zurück.
Sonst, def. den Gerichteter Graph $G'$ und $L$ wie in Maximal Matching bzgl. $M$ in $G$. Sei $\delta=\min_{i\in(A\cap L),j\in(B\setminus L)}w_{i,j}$. Da wir wissen dass $\delta> 0$ da:
1. keine Kante in $E$ zwischen $A\cap L$ und $B\setminus L$ existiert (da diese sonst nicht von der Knotenüberdeckung $C^*=(A\setminus L)\dot\cup(B\cap L)$ abgedeckt wäre) und
2. $L\not=\emptyset$ (da $M$ nicht perfekt ist).
Sei $$u'_i =\begin{cases}u_i &i\in A\setminus L\\ u_i + \delta &i\in A\cap L\end{cases}$$und$$v'_i =\begin{cases}v_j&j\in B\setminus L\\ v_j + \delta &j\in B\cap L\end{cases}$$die neue duale Lösung.

	\begin{algorithm}
	\caption{Gewichtetes Matching-Problem}
	\begin{algorithmic}
	\Input Bipartite graph $F$
    \Procedure{minimum-weighted-matching}{$F$}
	\State $u_i\gets 0\quad \forall i\in A$
	\State $v_j\gets \min_{i\in A}c_{i,j}\quad \forall j\in B$
	\While{TRUE}
		\State Let $G$ be the Graph induced by the edges $E=\left\{\{i,j\}\mid i\in A,j\in B,w_{i,j}=0\right\}$
		\State $M\gets$ \Call{Maximum-Match}{$G$}
		\If{$M$ is perfect matching}
		    \return $M$
		\Else
			\State Let $G'$ and $L$ be as defined in maximum matching w.r.t $M$ in $G$.
			\State $\delta\gets\min_{i\in(A\cap L),j\in(B\setminus L)}w_{i,j}$
			\State $u'_i =\begin{cases}u_i &i\in A\setminus L\\ u_i + \delta &i\in A\cap L\end{cases}$
			\State $v'_i =\begin{cases}v_j&j\in B\setminus L\\ v_j + \delta &j\in B\cap L\end{cases}$
			\State $u_i\gets u'_i\quad \forall i\in A$
			\State $v_j\gets v'_j\quad \forall j\in B$
	    \EndIf
    \EndWhile
    \EndProcedure
	\end{algorithmic}
	\end{algorithm}

Der Unterschied zwischen $(u,v)$ und $(u',v')$ ergibt sich als

$$\begin{align}&\delta(|A\cap L|-|B\cap L|) \\=& \delta(|A\cap L|+ |A\setminus L|-|A\setminus L|-|B\cap L|)&\Huge|\normalsize\text{Erweitert}\\=& \delta(|(A\cap L)\dot\cup(A\setminus L)|-|(A\setminus L)\dot\cup(B\cap L)|)&\Huge|\normalsize\text{Eig. Menge}\\=& \delta(|A|-|C^*|)&\Huge|\normalsize\text{Def. $A, C^*$}\\\end{align}$$

wobei $C^*$ die optimale Knotenüberdeckung von $E$ ist. Wir wissen als Annahme (if else) das $M$ nicht perfekt ist und daher $|C^*|=|M|<|A|$ was sich umformen lässt zu $|A|-|C^*|>0$. Das heißt der Zielwert wird stetig erhöht durch jede Iteration.

Da in jeder Iteration ein $w_{i,j}$ gleich Null gesetzt wird, wird ein neuer Knoten aus $B$ erreichbar bzw. das Matching vergrößert sich um eine Kante. Der Algortihmus hat also eine Laufzeit von $\mathcal O(n^2)$.

Home: