↑ arvau

Wikipedia / Set cover problem

The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory.

Given a set of elements (henceforth referred to as the universe, specifying all possible elements under consideration) and a collection, referred to as , of a given subsets whose union equals the universe, the set cover problem is to identify a smallest sub-collection of whose union equals the universe.

For example, consider the universe, and the collection of sets In this example, is equal to 4, as there are four subsets that comprise this collection. The union of is equal to . However, we can cover all elements with only two sets: , but not with only one set. Therefore, the solution to the set cover problem for this and has size 2. This example is illustrated in the picture above.

, a set cover.

The decision version of set covering is NP-complete. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972. The optimization/search version of set cover is NP-hard. It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms.

Variants

In the weighted set cover problem, each set is assigned a positive weight (representing its cost), and the goal is to find a set cover with a smallest weight. The usual (unweighted) set cover corresponds to all sets having a weight of 1.

In the fractional set cover, such that for each element x in the universe, the sum of fractions of sets that contain x is at least 1. The goal is to find a fractional set cover in which the sum of fractions is as small as possible. Note that a (usual) set cover is equivalent to a fractional set cover in which all fractions are either 0 or 1; therefore, the size of the smallest fractional cover is at most the size of the smallest cover, but may be smaller. For example, consider the universe and the collection of sets The smallest set cover has a size of 2, e.g. But there is a fractional set cover of size 1.5, in which a 0.5 fraction of each set is taken.

In the capacitated set cover which denotes the number of elements it can supply coverage. The goal is to determine the optimal way to select sets such that each element receives the coverage it requires.

Linear program formulationLP

The set cover problem can be formulated as the following integer linear program (ILP).For a more compact representation of the covering constraint, one can define an incidence matrix , where each row corresponds to an element and each column corresponds to a set, and if element e is in set s, and .

Weighted set cover.

Fractional set cover.

This linear program belongs to the more general class of LPs for covering problems, as all the coefficients in the objective function and both sides of the constraints are non-negative. The integrality gap is the size of the universe). It has been shown that its relaxation approximation algorithm for the minimum set cover problem. See setcover for a detailed explanation.

Hitting set formulation

is called a hitting set). The hitting set problem.

, and vice versa.

This equivalence can also be visualized by representing the problem as a bipartite graph-th vertex of the right iff.. These definitions are exactly the same except that left and right on the left side, creating a graph that is a mirror image of the one described above. This shows that set covers in the original graph are equivalent to hitting sets in the mirrored graph, and vice versa.

In the field of computational geometry, a hitting set for a collection of geometrical objects is also called a stabbing set or piercing set.

Greedy algorithm

There is a greedy algorithm for polynomial time approximation of set covering that chooses sets according to one rule: at each stage, choose the set that contains the largest number of uncovered elements. This method can be implemented in time linear in the sum of sizes of the input sets, using a bucket queue to prioritize the sets. is the size of the set to be covered. -th harmonic number

.

pairwise disjoint sets is pictured on the right.

Inapproximability results show that the greedy algorithm is essentially the best-possible polynomial time approximation algorithm for set cover up to lower order terms (see Inapproximability results.

Low-frequency systems

If each element occurs in at most sets, then a solution can be found in polynomial time that approximates the optimum to within a factor of using LP relaxation.

for all in the integer linear program shown above, then it becomes a (non-integer) linear program . The algorithm can be described as follows:

  1. Find an optimal solution for the program using some polynomial-time method of solving linear programs.

  2. Pick all sets for which the corresponding variable has value at least 1/ in the solution .

Inapproximability results

refers to the size of the universe, , unless NP has quasi-polynomial time algorithms. Feige under the same assumptions, which essentially matches the approximation ratio achieved by the greedy algorithm. is a certain constant, under the weaker assumption that PNP was recently proved by . unless PNP.

In low-frequency systems, . If the Unique games conjecture as proven by .

unless PNP of the greedy algorithm essentially tight in this case.

Weighted set cover

The greedy algorithm for the weighted set cover problem-th harmonic number.

sets, the deterministic LP rounding-approximation. It starts with the optimal solution to the linear programming relaxation of the problem stated above are selected to form an integer solution.

The primal-dual algorithm for the set cover problem is an iterative method is the maximum number of sets that any element belongs to.

Randomized rounding is the size of the universe.

References can be found in and.

Fractional set cover

Related problems

  • Hitting set is an equivalent reformulation of Set Cover.

  • Vertex cover is a special case of Hitting Set.

  • Edge cover is a special case of Set Cover.

  • Geometric set cover and the sets are induced by the intersection of the universe and geometric shapes (e.g., disks, rectangles).

  • Set packing is the problem of selecting the maximum number of sets that are pairwise disjoint.

  • Maximum coverage problem sets to cover as many elements as possible.

  • Dominating set is the problem of selecting a set of vertices (the dominating set) in a graph such that all other vertices are adjacent to at least one vertex in the dominating set. The Dominating set problem was shown to be NP complete through a reduction from Set cover.

  • Exact cover problem is to choose a set cover with no element included in more than one covering set.

  • Red-blue set cover is a generalization of Set Cover where elements in the universe are colored either red or blue, and the goal is to select a sub-collection of the given sets that covers all of the blue elements while covering the minimum number of red elements.

  • Set-cover abduction is a related problem where, given a set of observations and a set of hypotheses, the goal is to select a subset of the hypotheses whose effects include all of the observations.

  • Monotone dualization is a computational problem equivalent to either listing all minimal hitting sets or listing all minimal set covers of a given set family.

Notes

References

  • .

  • .

  • .

  • .

  • .