Maximum coverage problem

The maximum coverage problem is a classical question in computer science, computational complexity theory, and operations research. It is a problem that is widely taught in approximation algorithms. As input you are given several sets and a number k . The sets may have some elements in common. You must select at most k 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 k and a collection of sets S = \{S_1, S_2, \ldots, S_m\} . : Objective: Find a subset S' \subseteq S of sets, such that \left| S' \right| \leq k and the number of covered elements \left| \bigcup_{S_i \in S'}{S_i} \right| is maximized. The maximum coverage problem is NP-hard, and cannot be approximated to within 1 - \frac{1}{e} + o(1) \approx 0.632 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.

The maximum coverage problem is a classical question in computer science, computational complexity theory, and operations research. It is a problem that is widely taught in approximation algorithms. As input you are given several sets and a number k . The sets may have some elements in common. You must select at most k 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 k and a collection of sets S = \{S_1, S_2, \ldots, S_m\} . Objective: Find a subset S' \subseteq S of sets, such that \left| S' \right| \leq k and the number of covered elements \left| \bigcup_{S_i \in S'}{S_i} \right| is maximized. The maximum coverage problem is NP-hard, and cannot be approximated to within 1 - \frac{1}{e} + o(1) \approx 0.632 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. ==ILP formulation== The maximum coverage problem can be formulated as the following integer linear program. 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 1 - \frac{1}{e} . ln-approximability results show that the greedy algorithm is essentially the best-possible polynomial time approximation algorithm for maximum coverage unless P = NP . y_j \in \{0,1\} ; (if y_j=1 then e_j is covered) x_i \in \{0,1\} (if x_i=1 then S_i is selected for the cover). The greedy algorithm for the weighted maximum coverage at each stage chooses a set that contains the maximum weight of uncovered elements. This algorithm achieves an approximation ratio of 1 - \frac{1}{e} . y_j \in \{0,1\} ; (if y_j=1 then e_j is covered) x_i \in \{0,1\} (if x_i=1 then S_i is selected for the cover). A greedy algorithm will no longer produce solutions with a performance guarantee. Namely, the worst case behavior of this algorithm might be very far from the optimal solution. The approximation algorithm is extended by the following way. First, define a modified greedy algorithm, that selects the set S_i that has the best ratio of weighted uncovered elements to cost. Second, among covers of cardinality 1, 2, ..., k-1 , find the best cover that does not violate the budget. Call this cover H_1 . Third, find all covers of cardinality k that do not violate the budget. Using these covers of cardinality k as starting points, apply the modified greedy algorithm, maintaining the best cover found so far. Call this cover H_2 . At the end of the process, the approximate best cover will be either H_1 or H_2 . This algorithm achieves an approximation ratio of 1- {1 \over e} for values of k \geq 3 . This is the best possible approximation ratio unless NP \subseteq DTIME(n^{O(\log\log n)}) . \sum_{i} y_{ij} \leq 1 ; (element e_j=1 can only be covered by at most one set). \sum_{S_i} x_i \geq y_{ij} ; (if y_j > 0 then at least one set e_j \in S_i is selected). y_{ij} \in \{0,1\} ; (if y_{ij}=1 then e_j is covered by set S_i ) x_i \in \{0,1\} (if x_i=1 then S_i is selected for the cover).

Text derived from https://en.wikipedia.org/w/index.php?oldid=1316597962 under CC BY-SA 4.0; modifications have been made.