Maximum coverage problem: Difference between revisions

Revision as of 05:49, 27 August 2022

Revision as of 07:37, 3 December 2022

Line 10:

: 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 cannotcan be approximated within <math>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 [[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>