Maximum Coverage Task

See: Packing Task, NP-Hard Task, Approximation Algorithm, Weighted Maximum Coverage Task.

---

---

References

2013

• http://en.wikipedia.org/wiki/Maximum_coverage_problem
  • The maximum coverage problem is a classical question in computer science and computational complexity theory. It is a problem that is widely taught in approximation algorithms.

    As input you are given several sets and a number [math]\displaystyle{ k }[/math]. The sets may have some elements in common. You must select at most [math]\displaystyle{ k }[/math] of these sets such that the maximum number of elements are covered, i.e. the union of the selected sets has maximal size.

    Formally, (unweighted) Maximum Coverage

    • Instance: A number [math]\displaystyle{ k }[/math] and a collection of sets [math]\displaystyle{ S = S_1, S_2, \ldots, S_m }[/math].
    • Objective: Find a subset [math]\displaystyle{ S^{'} \subseteq S }[/math] of sets, such that [math]\displaystyle{ \left| S^{'} \right| \leq k }[/math] and the number of covered elements [math]\displaystyle{ \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]\displaystyle{ 1 - \frac{1}{e} + o(1) \approx 0.632 }[/math] under standard assumptions. This result essentially matches the approximation ratio achieved by the generic greedy algorithm used for maximization of submodular functions with a cardinality constraint.

____