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^{'}\subseteq S$ od skupova, takav da $\left|S^{'}\right|\leq k$ i da je broj pokrivenih elemenata $\left|\bigcup _{S_{i}\in S^{'}}{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(енгл. integer linear problem)

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}}\leq k$ ; (ne više od k skupova je odabrano).

$\sum _{\,e_{j}\in S_{i}}x_{i}\geq y_{j}$; (ako je $y_{j}>0$ onda je bar jedan skup $e_{j}\in S_{i}$ je označen).

$0\leq y_{j}\leq 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}}\leq k$; (ne više od k skupova je odabrano).

$\sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}$; (ako je $y_{j}\geq 0$ onda je bar jedan skup $e_{j}\in S_{i}$ odabran).

$0\leq y_{j}\leq 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}}\leq B$ ; (cena odabranih skupova koja ne može preći $B$).

$\sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}$; (ako je $y_{j}\geq 0$ onda je bar jedan skup $e_{j}\in S_{i}$ obabran).

$0\leq y_{j}\leq 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}}\leq B$; (cena odabranih skupova ne može da pređe $B$).

$\sum _{i}y_{ij}\leq 1$; (element $e_{j}=1$ moži biti pokriven samo jednim skupom).

$\sum _{S_{i}}x_{i}\geq y_{ij}$ ; (ako je $y_{j}\geq 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

• Vazirani, Vijay V. (2001). Approximation Algorithms. Springer-Verlag. ISBN 3-540-65367-8. 
• Uriel Feige, A Threshold of ln $n$ for Approximating Set Cover, Journal of the ACM (JACM). . 45 (4): 634 — 652,.  July 1998.