Maximum coverage problem: Difference between revisions

Revision as of 07:58, 1 September 2021

Revision as of 21:11, 9 December 2021

Line 11:

: 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{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_functionSubmodular set function#Optimization_problemsOptimization 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 85:

== References ==

* {{Cite book | last=Vazirani | first=Vijay V. | author-link=Vijay Vazirani | title=Approximation Algorithms | year=2001 | publisher=Springer-Verlag | isbn=978-3-540-65367-7 }}

== External links ==

[[Category:Set families]]