Maximum coverage problem: Difference between revisions

Revision as of 23:00, 23 October 2020

Latest revision as of 21:56, 27 December 2024

(10 intermediate revisions by 9 users not shown)

Line 9:

Formally, (unweighted) Maximum Coverage

: 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 to 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 29:

== 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{1}{e}</math>.<ref>{{cite book | last=Hochbaum | first=Dorit S. | authorlinkauthor-link=Dorit S. Hochbaum | editor-first=Dorit S. | editor-last=Hochbaum | year=1997 | chapter=Approximating Covering and Packing Problems: Set Cover, Vertex Cover, Independent Set, and Related Problems | title=Approximation Algorithms for NP-Hard Problems | publisher=PWS Publishing Company | ___location=Boston | isbn=978-053494968-6 | pages=94–143}}</ref> ln-approximability results show that the greedy algorithm is essentially the best-possible polynomial time approximation algorithm for maximum coverage unless <math>P = NP</math>.<ref>{{cite journal | last = Feige | first = Uriel | authorlinkauthor-link = Uriel Feige | title = A Threshold of ln ''n'' for Approximating Set Cover | journal = Journal of the ACM | volume = 45 | number = 4 |date=July 1998 | issn = 0004-5411 | pages = 634–652 | doi = 10.1145/285055.285059 | publisher = Association for Computing Machinery | ___location = New York, NY, USA| s2cid = 52827488 | doi-access = free }}</ref>

== Known extensions ==

The inapproximability results apply to all extensions of the maximum coverage problem since they hold the maximum coverage problem as a special case.

The Maximum Coverage Problem can be applied to road traffic situations; one such example is selecting which bus routes in a public transportation network should be installed with pothole detectors to maximise coverage, when only a limited number of sensors is available. This problem is a known extension of the Maximum Coverage Problem and was first explored in literature by Junade Ali and Vladimir Dyo.<ref>{{cite book|last1=Ali|first1=Junade|last2=Dyo|first2=Vladimir|title=Proceedings of the 14th International Joint Conference on e-Business and Telecommunications |chapter=Coverage and Mobile Sensor Placement for Vehicles on Predetermined Routes: A Greedy Heuristic Approach|journal=Proceedings of the 14th International Joint Conference on E-Business and Telecommunications|date=2017|volume=Volume 2: WINSYS|pages=83–88|doi=10.5220/0006469800830088|url=http://www.scitepress.org/DigitalLibrary/PublicationsDetail.aspx?ID=ddWw1NMB3VI%3d|isbn=978-989-758-261-5}}</ref>

== Weighted version ==

Line 84:

== References ==

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

[[Category:SetFamilies familiesof sets]]

== External links ==

[[Category:Set families]]

[[Category:NP-complete problems]]