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 = S1, S2, ..., Sm. Izlaz: Pronađen je podskup od skupova, takav da i da je broj pokrivenih elemenata maksimalan.
Problem maksimalne pokrivenosti je NP-težak, i ne može biti aproksimiran sa pod standardnim pretpostavkama. Ovaj rezultat u suštini odgovara složenosti dobijenoj pomoću generičkog pohlepnog algoritma.G. L. Nemhauser, L. A. Wolsey and M. L. Fisher. An analysis of approximations for maximizing submodular set functions I, Mathematical Programming 14 (1978), 265–294
Formulacija ILP()
Problem maksimalne pokrivenosti može biti formulisan kao sledeći linearni program sa celim brojevima:
. (maksimalna suma pokrivenih elemenata).
; (ne više od k skupova je odabrano).
; (ako je onda je bar jedan skup je označen).
; (ako je onda je pokriven)
(ako je onda 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 . In: Approximation algorithms for NP-hard problems, Boston, 94-143.. Rezultati pokazuju da je pohlepni algoritam, najbolji mogući algoritam, polinomijalne vremenske složenosti za problem maksimalne pokrivenostiFeige, U., "A threshold of ln n for approximating set cover", J. ACM 45, 634-652..
Verzija sa težinama U verziji sa težinama svaki element ima težinu . Zadatak je naći maksimalnu pokrivenost koja ima i maksimalnu težinu. Specijalan slučaj je slučaj kad su sve težine 1.
. (maksimalna suma sa težinama pokrivenih elemenata).
; (ne više od k skupova je odabrano).
; (ako je onda je bar jedan skup odabran).
; (ako je onda je pokriven)
(ako je onda 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 ..
Maksimalna pokrivenost sa ograničenjem
U maksimalnoj pokrivenosti sa ograničenjem, svaki element ima težinu , ali i svaki skup ima cenu . Umesto koje označava ograničenje broja skupova u pokrivenosti budžet je dat. Ovaj budžet ograničava težinu prekrivenosti koja može biti odabrana.
. (maksimalna suma sa težinama pokrivenih elemenata).
; (cena odabranih skupova koja ne može preći ).
; (ako je onda je bar jedan skup obabran).
; (ako je onda je pokriven)
(ako je onda je 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 . Ovo je najbolji moguća složenost, osim ako (). , 1 (Apr. 1999),.
Generalizovana maksimalna pokrivenost
U uopštenoj verziji problema maksimalne pokrivenosti svaki skup ima cenu , a element ima drukčiju težinu i cenu koja zavisi od skupa koj je pokriva. Ako je pokriven skupom težina je i njena cena je . Budžet je dat za cenu celokupnog rešenja.
. (maksimalna suma sa težinama pokrivenih elemenata u skupovima u kojima su pokriveni).
; (cena odabranih skupova ne može da pređe ).
; (element moži biti pokriven samo jednim skupom).
; (ako je onda je bar jedan skup odabran).
; (ako je onda je pokriven skupom )
(ako je onda je 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 .Cohen, R. and Katzir, L. 2008. The Generalized Maximum Coverage Problem. Inf. Process. Lett. 108, 1 (Sep. 2008), 15-22.
Povezani problemi Problem pokrivenosti skupa, pokrivanje svih elemenata sa što manje skupova.
Reference
Категорија:НП-комплетни проблеми