Content deleted Content added
Semihatakan (talk | contribs) m Operations research people like this problem too (see the 1st reference), added that to the intro. |
m its→it is |
||
Line 66:
=== Generalized maximum coverage algorithm ===
The algorithm uses the concept of residual cost/weight. The residual cost/weight is measured against a tentative solution and
The algorithm has several stages. First, find a solution using greedy algorithm. In each iteration of the greedy algorithm the tentative solution is added the set which contains the maximum residual weight of elements divided by the residual cost of these elements along with the residual cost of the set. Second, compare the solution gained by the first step to the best solution which uses a small number of sets. Third, return the best out of all examined solutions. This algorithm achieves an approximation ratio of <math>1-1/e - o(1)</math>.<ref>Cohen, R. and Katzir, L. 2008. [http://dx.doi.org/10.1016/j.ipl.2008.03.017 The Generalized Maximum Coverage Problem]. ''Inf. Process. Lett''. 108, 1 (Sep. 2008), 15-22.</ref>
| |||