pokrycie.tex

\section{Pokrycie zbioru}


Problem pokrycia zbioru jest problemem optymalizacyjnym związany z problemem alokacji zasobów. 
Przedstawimy zachłanny algorytm o logarytmicznym współczynniku aproksymacji rozwiązujący ten problem.\\


Dane dla problemu pokrycia zbioru to para $(U,\mathcal{S})$ oraz funkcja kosztu $c$. $U$, zwane uniwersum, jest skończonym zbiorem elementów, a $\mathcal{S}$ jest rodziną podzbiorów $U$, taką że:\\
\[ \bigcup\limits_{i=1}^{n} S_{i} = U \] \\
Mówimy, że podzbiór $S_{i} \in \mathcal{S}$ pokrywa elementy należące do $S_{i}$. 
Z kolei $c: S_{i} \rightarrow \mathbb{R} $, każdemu podzbiorowi $S_{i}$ określa cenę pokrycia swoich elementów.

Problem polega na znalezieniu podrodziny $\mathcal{T} \subseteq \mathcal{S}$, której elementy pokrywają cały zbiór $U$:
\[ U = \bigcup_{T \in \mathcal{T}} T \]  
Spośród wszystkich takich rozwiązań interesuje nas to, którego koszt $c(\mathcal{T})$ jest minimalny: \[ min(c(\mathcal{T})) = \sum\nolimits_{T \in \mathcal{T}} c(T) \]  \\


Mając zdefiniowaną cenę podzbior możemy zdefiniować cenę rynkową elementu, która będzie naszym kryterium wyboru podzbiorów.
Niech $e_{1}, e_{2}, ... , e_{n}$ będą elementami $U$ w porządku pokrycia przez algorytm.
Przez cenę rynkową $f_{i}$ elementu będziemy rozumieć średni koszt nowo pokrywanego elementu $e_{i}$ przez rozpartywany podzbiór $S_{i}$: \\
\begin{align*}
f_{i} &= \frac{c(S_{j_i})}{\left|S_{j_i} \setminus \bigcup_{j_{i} < k} S_{k} \right|},\\
\end{align*}
gdzie $S_{i}$ jest to $i-ty$ zbiór wybierany przez algorytm, $S_{j_i}$ jest pierwszym zbiore m pokrywającym $e_{i}$, czyli\\ $j_{i} = min \bigg\{ 1 \leq k < n : e_i \in S_k \setminus \bigcup\limits_{l=1}^{k-1} S_{l}  \bigg\}$.\\
Mówiąc cena rynkowa zbioru mamy na myśli cenę rynkową elementów tego zbioru.\\


\begin{algorithm}[H]
  \DontPrintSemicolon
  \SetAlgorithmName{Algorytm}{}\\
  \KwData{ $U$ - uniwersum, $\mathcal{S}$ - rodzina podzbiorów $U$ }\\
  \KwResult{ $\mathcal{T}$, takie że $c(\mathcal{T})$ jest minimalne }\\
$\mathcal{T} \leftarrow \emptyset$  \\
  \While{$\mathcal{T} \neq U$}
  {
     Oblicz cenę rynkową dla wszystkich zbiorów\\
     Wybierz zbiór $A$ o najniższej cenie rynkowej\\
     $\mathcal{T} \leftarrow \mathcal{T} \cup A$ 
  }
  \caption{Zachłanny algorytm dla problemu pokrycia zbioru}
  \label{alg-pokrycie}
\end{algorithm}

\begin{lemma}
$f_{i} \leq \frac{c(OPT)}{n-i+1}$, gdzie $OPT$ jest rozwiązaniem optymalnym.\\
\end{lemma}
\begin{proof}
Gdyby do pokrycia elementu $e_i$ oraz wszystkich pozostałych elementów, czyli $e_{i+1}, e_{i+2}, ... , e_{n}$ użyłby rodziny zbiorów $OPT$, to cena rynkowa dla każdego z tych elementów wyniosłaby $\frac{c(OPT)}{libcza \ nowo \ pokrytych \ elementów}$, czyli $\frac{c(OPT)}{n-i+1}$.\\
W szczególności istnieje zbiór $Y \in OPT$ taki, że cena rynkowa pokrywanego elementu jest nie większa niż dla całego $OPT$.
Zatem algorytm zachłanny wybiera do pokrycia $e_i$ zbiór o cenie rynkowej pokrywanych elementów $\leq \frac{c(OPT)}{n-i+1}$.
\end{proof}
Koszt algorytmu zachłannego ALG \\
\begin{align*}
c(ALG) &= \sum_{i=1}^{n} f_i \\ &\leq  
\sum_{i=1}^{n} \frac{c(OPT)}{n-i+1}\\ &= 
c(OPT) \cdot \sum_{i=1}^{n} \frac{1}{n-i+1}\\ &=
 c(OPT) \cdot \sum_{i=1}^{n} \frac{1}{i}\\ &=
  c(OPT) \cdot H_n \\ &\leq c(OPT) \cdot \log(n+1)\\
\end{align*}