Problem maksimalne pokrivenosti

Problem maksimalne pokrivenosti je dobro poznat problem u polju informatike, teorije kompleksnosti i operacionom istraživanju. Kod ovog problema kao ulaz nam je dato nekoliko skupova i broj k. Skupovi mogu imati neke zajedničke elemente. Treba odabrati najviše k tih skupova, tako da je maksimalan broj elemenata pokriven, tj unija odabranih skupova ima maksimalnu veličinu.

Formalna, (beztežinska verzija)problema maksimalne pokrivenost je:

Ulaz: Broj k i kolekcija skupova S = S₁, S₂, ..., S_m.
Izlaz: Pronađen je podskup $S^{\text{'}}\subseteq S$ od skupova, takav da $\left|S^{\text{'}}\right|\le k$ i da je broj pokrivenih elemenata $\left|\bigcup _{S_i\in S^{\text{'}}}{S}_i\right|$ maksimalan.

Problem maksimalne pokrivenosti je NP-težak, i ne može biti aproksimiran sa $1-\frac{1}{e}+o(1)\approx 0.632$ pod standardnim pretpostavkama. Ovaj rezultat u suštini odgovara složenosti dobijenoj pomoću generičkog pohlepnog algoritma.

Formulacija ILP(Шаблон:Јез-енг)

Problem maksimalne pokrivenosti može biti formulisan kao sledeći linearni program sa celim brojevima:

$\sum _{e_j\in E}{y}_j$. (maksimalna suma pokrivenih elemenata).

$\sum x_i\le k$ ; (ne više od k skupova je odabrano).

$\sum _{e_j\in S_i}{x}_i\ge y_j$; (ako je $y_j>0$ onda je bar jedan skup $e_j\in S_i$ je označen).

$0\le y_j\le 1$; (ako je $y_j=1$ onda je $e_j$ pokriven)

$x_i\in \{0,1\}$ (ako je $x_i=1$ onda $S_i$ je odabran za prekrivenost).

Pohlepni algoritam

Pohlepni algoritam za maksimalnu pokrivenost bira skupove vodeći se jednim pravilom: u svakom koraku, biramo skup sa najviše nepokrivenih elemenata. Može se pokazati da ovaj algoritam dostiže složenost od $1-\frac{1}{e}$. Rezultati pokazuju da je pohlepni algoritam, najbolji mogući algoritam, polinomijalne vremenske složenosti za problem maksimalne pokrivenosti.

Verzija sa težinama

U verziji sa težinama svaki element $e_j$ ima težinu $w(e_j)$. Zadatak je naći maksimalnu pokrivenost koja ima i maksimalnu težinu. Specijalan slučaj je slučaj kad su sve težine 1.

$\sum _{e\in E}w(e_j)\cdot y_j$. (maksimalna suma sa težinama pokrivenih elemenata).

$\sum x_i\le k$; (ne više od k skupova je odabrano).

$\sum _{e_j\in S_i}{x}_i\ge y_j$; (ako je $y_j\ge 0$ onda je bar jedan skup $e_j\in S_i$ odabran).

$0\le y_j\le 1$; (ako je $y_j=1$ onda je $e_j$ pokriven)

$x_i\in \{0,1\}$ (ako je $x_i=1$ onda $S_i$ odabran za prekrivenost).

Pohlepni algoritam u verziji sa težinama pri problemu maksimalne pokrivenosti u svakom koraku bira skup koj sadrži maksimalnu težinu nepokrivenih elemenata. Ovaj algoritam postiže složenost $1-\frac{1}{e}$..

Maksimalna pokrivenost sa ograničenjem

U maksimalnoj pokrivenosti sa ograničenjem, svaki element $e_j$ ima težinu $w(e_j)$, ali i svaki skup $S_i$ ima cenu $c(S_i)$. Umesto $k$ koje označava ograničenje broja skupova u pokrivenosti $a$ budžet $B$ je dat. Ovaj budžet $B$ ograničava težinu prekrivenosti koja može biti odabrana.

$\sum _{e\in E}w(e_j)\cdot y_j$. (maksimalna suma sa težinama pokrivenih elemenata).

$\sum c(S_i)\cdot x_i\le B$ ; (cena odabranih skupova koja ne može preći $B$).

$\sum _{e_j\in S_i}{x}_i\ge y_j$; (ako je $y_j\ge 0$ onda je bar jedan skup $e_j\in S_i$ obabran).

$0\le y_j\le 1$; (ako je $y_j=1$ onda je $e_j$ pokriven)

$x_i\in \{0,1\}$ (ako je $x_i=1$ onda je $S_i$ odabran za pokrivenost).

Pohlepan algoritam nam neće više dostavljati rešenje sa garantovanom dobrom preformansom. U najgorem mogućem slučaju izvođenje ovog algoritma može biti daleko od optimalnog rešenja. Algoritam aproksimacije proširujemo na sledeći način: Prvo, posle pronalaska rešenja koristeći pohlepni algoritam, vraća se najbolje od rešenja pohlepnog algoritma i skup najveće težine. Ovo možemo nazvati modifikovani pohlepni algoritam. Drugo, počev od svih mogućih familija skupova sa veličinama od 1 do bar 3, povećati rešenja uz pomoć modifikovanog pohlepnog algoritma. Treće, vrati najbolji od svih povećanih rešenja. Ovaj algoritam dostiže složenost $1-1/e$. Ovo je najbolji moguća složenost, osim ako $NP\subseteq DTIME$($n^{O(\log \log n)}$).

Generalizovana maksimalna pokrivenost

U uopštenoj verziji problema maksimalne pokrivenosti svaki skup $S_i$ ima cenu $c(S_i)$, a element $e_j$ ima drukčiju težinu i cenu koja zavisi od skupa koj je pokriva. Ako je $e_j$ pokriven skupom $S_i$ težina $e_j$ je $w_i(e_j)$ i njena cena je $c_i(e_j)$. Budžet $B$ je dat za cenu celokupnog rešenja.

$\sum _{e\in E,S_i}{w}_i(e_j)\cdot y_{ij}$. (maksimalna suma sa težinama pokrivenih elemenata u skupovima u kojima su pokriveni).

$\sum c_i(e_j)\cdot y_{ij}+\sum c(S_i)\cdot x_i\le B$; (cena odabranih skupova ne može da pređe $B$).

$\sum _i{y}_{ij}\le 1$; (element $e_j=1$ moži biti pokriven samo jednim skupom).

$\sum _{S_i}{x}_i\ge y_{ij}$ ; (ako je $y_j\ge 0$ onda je bar jedan skup $e_j\in S_i$ odabran).

$y_{ij}\in \{0,1\}$ ; (ako je $y_{ij}=1$ onda je $e_j$ pokriven skupom $S_i$)

$x_i\in \{0,1\}$(ako je $x_i=1$ onda je $S_i$ odabran za prekrivenost).

Algoritam

Algoritam koristi koncept ostatka cene/težine. Ostatak cene/težine je meren sa privremenim rešenjem i to je razlika cene/težine od cene/težine dobijene u privremenom rešenju.

Algoritam ima nekoliko koraka. Prvo, pronaći rešenje korišćenjem pohlepnog algoritma. U svakoj iteraciji pohlepnog algoritma privremeno rešenje je dodato skupu koji sadrži maksimum ostatak težina elemenata, podeljenog sa ostatkom cena ovih elemenata, zajedno sa ostatkom cene skupa. Drugo, porediti rešenja dobijena u prvom koraku tako da se dobije najbolje rešenje od njih koje koristi mali broj skupova. Treće, vrati najbolji od proverenih rešenja. Ovaj algoritam dostiže složenost od $1-1/e-o(1)$.

Povezani problemi

• Problem pokrivenosti skupa, pokrivanje svih elemenata sa što manje skupova.

Reference

• Шаблон:Cite book
• Uriel Feige, A Threshold of ln $n$ for Approximating Set Cover, Journal of the ACM (JACM). Шаблон:Cite journalJuly 1998.