Maximum coverage problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 . The sets may have some elements in common. You must select at most 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 and a collection of sets .
Objective: Find a subset of sets, such that and the number of covered elements is maximized.

The maximum coverage problem is NP-hard, and cannot be approximated within 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.[1]

ILP formulation[edit]

The maximum coverage problem can be formulated as the following integer linear program.

maximize (maximizing the sum of covered elements)
subject to (no more than sets are selected)
(if then at least one set is selected)
(if then is covered)
(if then is selected for the cover)

Greedy algorithm[edit]

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 .[2] Inapproximability results show that the greedy algorithm is essentially the best-possible polynomial time approximation algorithm for maximum coverage.[3]

Known extensions[edit]

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

Weighted version[edit]

In the weighted version every element has a weight . The task is to find a maximum coverage which has maximum weight. The basic version is a special case when all weights are .

maximize . (maximizing the weighted sum of covered elements).
subject to ; (no more than sets are selected).
; (if then at least one set is selected).
; (if then is covered)
(if then 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]

Budgeted maximum coverage[edit]

In the budgeted maximum coverage version, not only does every element have a weight , but also every set has a cost . Instead of that limits the number of sets in the cover a budget is given. This budget limits the total cost of the cover that can be chosen.

maximize . (maximizing the weighted sum of covered elements).
subject to ; (the cost of the selected sets cannot exceed ).
; (if then at least one set is selected).
; (if then is covered)
(if then 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 that has the best ratio of weighted uncovered elements to cost. Second, among covers of cardinality , find the best cover that does not violate the budget. Call this cover . Third, find all covers of cardinality that do not violate the budget. Using these covers of cardinality as starting points, apply the modified greedy algorithm, maintaining the best cover found so far. Call this cover . At the end of the process, the approximate best cover will be either or . This algorithm achieves an approximation ratio of for values of . This is the best possible approximation ratio unless .[4]

Generalized maximum coverage[edit]

In the generalized maximum coverage version every set has a cost , element has a different weight and cost depending on which set covers it. Namely, if is covered by set the weight of is and its cost is . A budget is given for the total cost of the solution.

maximize . (maximizing the weighted sum of covered elements in the sets in which they are covered).
subject to ; (the cost of the selected sets cannot exceed ).
; (element can only be covered by at most one set).
; (if then at least one set is selected).
; (if then is covered by set )
(if then is selected for the cover).

Generalized maximum coverage algorithm[edit]

The algorithm uses the concept of residual cost/weight. The residual cost/weight is measured against a tentative solution and it is the difference of the cost/weight from the cost/weight gained by a tentative solution.

The algorithm has several stages. First, find a solution using greedy algorithm. In each iteration of the greedy algorithm the tentative solution is added the set which contains the maximum residual weight of elements divided by the residual cost of these elements along with the residual cost of the set. Second, compare the solution gained by the first step to the best solution which uses a small number of sets. Third, return the best out of all examined solutions. This algorithm achieves an approximation ratio of .[5]

Related problems[edit]

Notes[edit]

  1. ^ a b 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
  2. ^ Hochbaum, Dorit S. (1997). "Approximating Covering and Packing Problems: Set Cover, Vertex Cover, Independent Set, and Related Problems". In Hochbaum, Dorit S. Approximation Algorithms for NP-Hard Problems. Boston: PWS Publishing Company. pp. 94–143. ISBN 053494968-1. 
  3. ^ Feige, Uriel (July 1998). "A Threshold of ln n for Approximating Set Cover". Journal of the ACM. 45 (4). New York, NY, USA: Association for Computing Machinery. pp. 634–652. ISSN 0004-5411. doi:10.1145/285055.285059. 
  4. ^ Khuller, S., Moss, A., and Naor, J. 1999. The budgeted maximum coverage problem. Inf. Process. Lett. 70, 1 (Apr. 1999), 39-45.
  5. ^ Cohen, R. and Katzir, L. 2008. The Generalized Maximum Coverage Problem. Inf. Process. Lett. 108, 1 (Sep. 2008), 15-22.

References[edit]

External links[edit]