Maximum coverage problem: Difference between revisions

Revision as of 09:19, 4 July 2012

Revision as of 02:24, 15 October 2012

Line 12:

: Instance: A number <math> k </math> and a collection of sets <math> S = S_1, S_2, \ldots, S_m </math>.

: Objective: Find a subset <math> S^{'} \subseteq S</math> of sets, such that <math> \left| S^{'} \right| \leq k</math> and the number of covered elements <math> \left| \bigcup_{S_i \in S^{'}}{S_i} \right| </math> is maximized.

The maximum coverage problem is [[NP-hard]], and cannot be approximated within <math>1 - \frac{e1}{e-1}- + o(1) \approx 10.58632</math> under standard assumptions.

This result essentially matches the approximation ratio achieved by the generic greedy algorithm used for [[Submodular_set_function#Optimization_problems|maximization of submodular functions with a cardinality constraint]].<ref name="NVF"> [[George Nemhauser|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</ref>

==ILP formulation==

Line 25:

== Greedy algorithm ==

The [[greedy algorithm]] for maximum coverage chooses sets according to one rule: at each stage, choose a set which contains the largest number of uncovered elements. It can be shown that this algorithm achieves an approximation ratio of <math>1 - \frac{e1}{e-1}</math>.<ref>Hochbaum, D. S. (1997), "Approximating covering and packing problems: Set cover, vertex cover, independent set, and related problems", in Approximation algorithms for NP-hard problems, PWS Publishing Company, Boston, 94-143. </ref>

Inapproximability results show that the greedy algorithm is essentially the best-possible polynomial time approximation

algorithm for maximum coverage.<ref>Feige, U., "A threshold of ln n for approximating set cover", J. ACM 45, 634-652. </ref>

Line 41:

::<math>x_i \in \{0,1\}</math> (if <math>x_i=1</math> then <math>S_i</math> is selected for the cover).

The greedy algorithm for the weighted maximum coverage at each stage chooses a set which contains the maximum weight of uncovered elements. This algorithm achieves an approximation ratio of <math>1 - \frac{e1}{e-1}</math>.{{Citation<ref needed|datename=November 2009}}"NVF"/>

== Budgeted maximum coverage ==

In the budgeted maximum coverage version, not only does every element <math> e_j </math> have a weight <math>w(e_j)</math>, but also every set <math>S_i</math> has a cost <math>c(S_i)</math>. Instead of <math>k</math> that limits the number of sets in the cover a budget <math>B</math> is given. This budget <math>B</math> limits the weight of the cover that can be chosen.