Set cover problem

Example of an instance of 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 {1, 2, …, n} (henceforth referred to as the universe, specifying all possible elements under consideration) and a collection, referred to as S whose union equals the universe.

For example, consider the universe, }</nowiki>"}},"i":0}}]}'/>U = {1, 2, 3, 4, 5} and the collection of sets S is equal to U and 𝒮 of subsets of 𝒰.

• In the set cover decision problem, the input is a pair k or less.
• In the set cover optimization problem, the input is a pair 𝒮, 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 }</nowiki>"}},"i":0}}]}'/>U = {1, 2, 3} and the collection of sets
  • v
  • t
  • e

  In the capacitated set cover problem, each set ∑s∈𝒮xs (minimize the number of sets) subject to xs∈{0,1} for all Ae,s=1 if element e is in set s, and ∑s∈𝒮wsxs, where xs can be non-integer, so the last constraint is replaced by n is the size of the universe). It has been shown that its relaxation indeed gives a factor-U is called a hitting set when H intersects or "hits" all subsets in U and n and collection of sets U′={1,2,…,m} and S is equivalent to a hitting set Sj∈C⟺j∈H′, and vice versa.

  This equivalence can also be visualized by representing the problem as a bipartite graph of U, and i-th vertex on the left and the C of right vertices such that each left vertex is adjacent to at least one member of H. These definitions are exactly the same except that left and right are swapped. But there is nothing special about the sides in the bipartite graph; we could have put the elements of H(s), where H(n) is the H(s′) where δ−dense instances, however, there exists a log2(n)/2. The universe consists of S1,…,Sk with sizes Si. On this input, the greedy algorithm takes the sets T1. An example of such an input for f sets, then a solution can be found in polynomial time that approximates the optimum to within a factor of xS≥0 for all L. The algorithm can be described as follows:

  1. Find an optimal solution S for which the corresponding variable f in the solution 12log2n≈0.72ln⁡n, unless NP has quasi-polynomial time algorithms. Feige (1998) improved this lower bound to c is a certain constant, under the weaker assumption that P(1−o(1))⋅ln⁡n unless Pf−ϵ as proven by Khot & Regev (2008).

     Trevisan (2001) proves that set cover instances with sets of size at most =NP, thus making the approximation of 𝒮 of subsets of 𝒰 are uncovered. At each iteration, the algorithm selects a set H(n) times the optimal solution, where n=|𝒰|.

     For low frequency systems, where every element is contained in at most 1/f are selected to form an integer solution.

     The primal-dual algorithm for the set cover problem is an iterative method that constructs feasible solutions to both the primal and dual linear programs simultaneously. Starting with all dual variables set to zero, the algorithm repeatedly increases the dual variables corresponding to uncovered elements uniformly, until some set's dual constraint becomes tight (i.e., the sum of the dual variables for elements in the set equals its cost). This tight set is then added to the primal solution, covering the corresponding elements. The process continues until all elements are covered. The algorithm guarantees an approximation ratio of xS∗ be an optimal fractional solution to the LP relaxation. Each set O(log⁡n) factor of the optimal solution, where

     [</span>icon<span typeof=\"mw:Entity\" id=\"mwAYY\">]</span>","txt":"[icon]"}]]}'>

     Related problems

     edit
     • 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 is a special case of Set Cover when the universe is a set of points in
       1. ↑ Korte & Vygen 2012, p. 414.
       2. ↑ Vazirani (2001, p. 15)
       3. ↑ Vazirani (2001, p. 108)
       4. ↑ Vazirani (2001, pp. 110–112)
       5. ↑ Nielsen, Frank (2000-09-06). "Fast stabbing of boxes in high dimensions" (PDF). Theoretical Computer Science. 246 (1): 53–72. doi:10.1016/S0304-3975(98)00336-3. ISSN 0304-3975.
       6. ↑ Johnson, D. S. (1974), "Approximation algorithms for combinatorial problems", Journal of Computer and System Sciences, 9 (3): 256–278, Bibcode:1974JCoSS...9..256J, doi:10.1016/S0022-0000(74)80044-9
       7. ↑ Hochbaum, Dorit S. (1982), "Approximation algorithms for the Set Covering and Vertex Cover problems", SIAM Journal on Computing, 11 (3): 555–556, doi:10.1137/0211045, ISSN 0097-5397
       8. ↑ Williamson, David P.; Shmoys, David B. (2011), The Design of Approximation Algorithms, Cambridge University Press, ISBN 978-0-521-19578-7{{citation}}: Check |isbn= value: checksum (help)
       9. ↑ Alon, Noga; Moshkovitz, Dana; Safra, Shmuel (2006), "Algorithmic construction of sets for k-restrictions", ACM Trans. Algorithms, 2 (2): 153–177, doi:10.1145/1150334.1150336, ISSN 1549-6325, S2CID 11922650.
       10. Karpinski, Marek; Zelikovsky, Alexander (1998), "Approximating dense cases of covering problems", Proceedings of the DIMACS Workshop on Network Design: Connectivity and Facilities Location, vol. 40, American Mathematical Society, pp. 169–178, ISBN 978-0-8218-7084-6
       11. Korte, Bernhard; Vygen, Jens (2012), Combinatorial Optimization: Theory and Algorithms (5 ed.), Springer, ISBN 978-3-642-24487-2
       12. Khot, Subhash; Regev, Oded (2008), Vertex cover might be hard to approximate to within 2−