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 ${\displaystyle S^{'}\subseteq S}$ od skupova, takav da ${\displaystyle \left|S^{'}\right|\leq k}$ i da je broj pokrivenih elemenata ${\displaystyle \left|\bigcup _{S_{i}\in S^{'}}{S_{i}}\right|}$ maksimalan.

Problem maksimalne pokrivenosti je NP-težak, i ne može biti aproksimiran sa ${\displaystyle 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.^[1]

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

${\displaystyle \sum _{e_{j}\in E}y_{j}}$. (maksimalna suma pokrivenih elemenata).

${\displaystyle \sum {x_{i}}\leq k}$ ; (ne više od k skupova je odabrano).

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

${\displaystyle 0\leq y_{j}\leq 1}$; (ako je ${\displaystyle y_{j}=1}$ onda je ${\displaystyle e_{j}}$ pokriven)

${\displaystyle x_{i}\in \{0,1\}}$ (ako je ${\displaystyle x_{i}=1}$ onda ${\displaystyle S_{i}}$ je odabran za prekrivenost).

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 ${\displaystyle 1-{\frac {1}{e}}}$^[2]. Rezultati pokazuju da je pohlepni algoritam, najbolji mogući algoritam, polinomijalne vremenske složenosti za problem maksimalne pokrivenosti^[3].

U verziji sa težinama svaki element ${\displaystyle e_{j}}$ ima težinu ${\displaystyle 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.

${\displaystyle \sum _{e\in E}w(e_{j})\cdot y_{j}}$. (maksimalna suma sa težinama pokrivenih elemenata).

${\displaystyle \sum {x_{i}}\leq k}$; (ne više od k skupova je odabrano).

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

${\displaystyle 0\leq y_{j}\leq 1}$; (ako je ${\displaystyle y_{j}=1}$ onda je ${\displaystyle e_{j}}$ pokriven)

${\displaystyle x_{i}\in \{0,1\}}$ (ako je ${\displaystyle x_{i}=1}$ onda ${\displaystyle 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 ${\displaystyle 1-{\frac {1}{e}}}$.^[1].

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

${\displaystyle \sum _{e\in E}w(e_{j})\cdot y_{j}}$. (maksimalna suma sa težinama pokrivenih elemenata).

${\displaystyle \sum {c(S_{i})\cdot x_{i}}\leq B}$ ; (cena odabranih skupova koja ne može preći ${\displaystyle B}$).

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

${\displaystyle 0\leq y_{j}\leq 1}$; (ako je ${\displaystyle y_{j}=1}$ onda je ${\displaystyle e_{j}}$ pokriven)

${\displaystyle x_{i}\in \{0,1\}}$ (ako je ${\displaystyle x_{i}=1}$ onda je ${\displaystyle 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 ${\displaystyle 1-1/e}$. Ovo je najbolji moguća složenost, osim ako ${\displaystyle NP\subseteq DTIME}$(${\displaystyle n^{O(\log \log n)}}$).^[4]

U uopštenoj verziji problema maksimalne pokrivenosti svaki skup ${\displaystyle S_{i}}$ ima cenu ${\displaystyle c(S_{i})}$, a element ${\displaystyle e_{j}}$ ima drukčiju težinu i cenu koja zavisi od skupa koj je pokriva. Ako je ${\displaystyle e_{j}}$ pokriven skupom ${\displaystyle S_{i}}$ težina ${\displaystyle e_{j}}$ je ${\displaystyle w_{i}(e_{j})}$ i njena cena je ${\displaystyle c_{i}(e_{j})}$. Budžet ${\displaystyle B}$ je dat za cenu celokupnog rešenja.

${\displaystyle \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).

${\displaystyle \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 ${\displaystyle B}$).

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

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

${\displaystyle y_{ij}\in \{0,1\}}$ ; (ako je ${\displaystyle y_{ij}=1}$ onda je ${\displaystyle e_{j}}$ pokriven skupom ${\displaystyle S_{i}}$)

${\displaystyle x_{i}\in \{0,1\}}$(ako je ${\displaystyle x_{i}=1}$ onda je ${\displaystyle S_{i}}$ odabran za prekrivenost).

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 ${\displaystyle 1-1/e-o(1)}$.^[5]

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

• Vazirani, Vijay V. (2001). Approximation Algorithms. Springer-Verlag. ISBN 3-540-65367-8. 
• Uriel Feige, A Threshold of ln ${\displaystyle n}$ for Approximating Set Cover, Journal of the ACM (JACM). . 45 (4): 634 — 652,.  Недостаје или је празан параметар |title= (помоћ)July 1998.