[Enunciado]
O seguinte algoritmo
calcula uma cobertura de custo aproximadamente mínimo
num grafo com custos nos vértices.
Para expor o algoritmo precisamos de um pouco de notação. Suponha que cada aresta $ij$ do grafo tem um peso racional $y(ij) \geq 0\text{.}$ Vamos estender o domínio de $y$ ao conjunto de vértices do grafo: para cada vértice $v\text{,}$ seja \begin{equation}\textstyle y[v] := \sum_{vw\in E}\, y(vw)\,. \label{eq:def} \end{equation}
Podemos agora descrever o
algoritmo de Bar-Yehuda e Even
para o problema da cobertura de custo mínimo.
O algoritmo se baseia no método primal-dual
derivado da teoria da dualidade da programação linear
(embora nenhum programa linear apareça
explicitamente no algoritmo).
Cada iteração do algoritmo começa com um peso racional não-negativo $y(ij)$ associado a cada aresta $ij\text{.}$ O algoritmo procura aumentar esses pesos obedecendo a restrição \[ y[v] \leq c(v) \] para todo vértice $v$ do grafo. Diremos que o vértice $v$ está justo (em relação a um dado $y$) se $y[v] = c(v)\text{.}$
| 1Cobertura-Aproximadamente-Mínima$\,(G, c)$ |
| 11 . $Y := \emptyset$ |
| 12 . para cada $vw$ em $E(G)$ |
| 13 .ooo faça $y(vw) := 0$ |
| 14 . enquanto $E(G - Y) \neq \emptyset$ |
| 15 .ooo tome $vw$ em $E(G - Y)$ |
| 16 .ooo $\varepsilon := \min\, (c(v) - y[v],\, c(w) - y[w])$ |
| 17 .ooo $y(vw) := y(vw) + \varepsilon$ |
| 18 .ooo se $y[v]=c(v)$ então $Y := Y\cup\conj{v}$ |
| 19 .ooo se $y[w]=c(w)$ então $Y := Y\cup\conj{w}$ |
| 10 . devolva $Y$ |
O processo iterativo nas linhas 4 a 9 tem os seguintes invariantes: no início de cada iteração,
Na linha 10, o conjunto $Y$ é uma cobertura (pois $E(G-Y)=\emptyset$). Graças ao invariante 2 e à definição \eqref{eq:def}, o custo dessa cobertura é \begin{align} c(Y) & = \textstyle \sum_{v\in Y}\, c(v) \nonumber\\[0.5ex] & = \textstyle \sum_{v\in Y}\, y[v] \nonumber\\[0.5ex] & = \textstyle \sum_{v\in Y}\, \big( \sum_{vw\in E}\, y(vw) \big) \label{um}\\[0.5ex] &\leq \textstyle 2\,\sum_{ij\in E}\, y(ij)\,. \nonumber \end{align} A última desigualdade vale porque cada aresta contribui no máximo duas parcelas para a soma \eqref{um}: uma parcela se tiver uma só ponta em $Y$ e duas parcelas se tiver ambas as pontas em $Y\text{.}$ Por outro lado, para qualquer cobertura $C\text{,}$ graças ao invariante 1, temos \begin{align} c(C) & = \textstyle \sum_{v\in C}\, c(v) \nonumber\\[0.5ex] &\geq \textstyle \sum_{v\in C}\, y[v] \nonumber\\[0.5ex] &= \textstyle \sum_{v\in C} \sum_{iv\in E} \, y(iv)\label{dois}\\[0.5ex] &\geq \textstyle \sum_{ij\in E}\, y(ij)\nonumber\,, \end{align} uma vez que cada aresta $ij$ tem pelo menos uma ponta em $C$ e portanto contribui pelo menos uma parcela para a soma (\ref{dois}). (A desigualdade $c(C)\geq \sum y(ij)$ nada mais é que uma manifestação da dualidade de programação linear.)
Segue daí que $c(Y)\leq 2\,c(C)$ para qualquer cobertura $C\text{.}$ Em particular, \[ c(Y) \leq 2\,c(X) \] quando $X$ é uma cobertura de custo mínimo. O algoritmo é, portanto, uma 2-aproximação para o problema da cobertura de custo mínimo.
Consumo de tempo. O algoritmo é polinomial: ele consome tempo limitado por $\Oh(mn) = \Oh(n^3)\text{,}$ sendo $m:=|E|$ e $n:=|V|\text{.}$