Computer Science
Set Cover Problem
The Set Cover Problem is a computational problem that involves finding the smallest set of subsets that can cover a larger set. It is a well-known NP-complete problem that has applications in various fields, including operations research, network design, and genetics. The problem is challenging because it requires finding an optimal solution from a large number of possible combinations.
Written by Perlego with AI-assistance
Related key terms
1 of 5
5 Key excerpts on "Set Cover Problem"
eBook - PDF- Michael T. Goodrich, Roberto Tamassia(Authors)
- 2014(Publication Date)
- Wiley(Publisher)
In this section, we study one of the best known of such problems, the SET-COVER problem (Section 17.4). In the optimization version of this problem, we are given a collection of sets S 1 , S 2 , . . . , S m , whose union is a universe U of size n, and we are asked to find the smallest integer k, such that there is a subcollection of k sets S i 1 , S i 2 , . . . , S i k with U = m i=1 S i = k j =1 S i j . Although it is difficult to find a constant-factor approximation algorithm that runs in polynomial time for this problem, we can design an efficient algorithm that has an approximation factor of O(log n). As with several other approximation algorithms for hard problems, this algorithm is based on the greedy method (Section 10). A Greedy Approach Our algorithm selects sets one at a time, each time selecting the set that has the most uncovered elements. When every element in U is covered, we are done. We give a simple pseudocode description in Algorithm 18.7. Algorithm SetCoverApprox(S ): Input: A collection S of sets S 1 , S 2 , . . . , S m whose union is U Output: A small set cover C for S C ← ∅ // The set cover built so far E ← ∅ // The elements from U currently covered by C while E = U do select a set S i that has the maximum number of uncovered elements add S i to C E ← E ∪ S i Return C . Algorithm 18.7: An approximation algorithm for SET-COVER. This algorithm runs in polynomial time. (See Exercise R-18.2.) To analyze the approximation factor of the above greedy SET-COVER algorithm, we will use an amortization argument based on a charging scheme (Section 1.4). Namely, each time our approximation algorithm selects a set S j , we will charge the elements of S j for its selection. 18.2. Approximations for Covering Problems 517 Specifically, consider the moment in our algorithm when a set S j is added to C , and let k be the number of previously uncovered elements in S j .
eBook - PDFCombinatorial Optimization and Theoretical Computer Science
Interfaces and Perspectives
- Vangelis Th. Paschos(Author)
- 2010(Publication Date)
- Wiley-ISTE(Publisher)
3.9. Bibliography [ALO 03] ALON N., AWERBUCH B., AZAR Y., BUCHVINDER N., NAOR S., “The online Set Cover Problem”, Proc. STOC’03, p. 100–105, 2003. 1. Given a graph G(V, E) the minimum dominating set problem consists of determining a minimum-size subset V ⊆ V such that, for all u ∈ V \ V , there exists v ∈ V for which (u, v) ∈ E. 92 Optimization and Computer Science [CHV 79] CHVÁTAL V., “A greedy-heuristic for the set covering problem”, Math. Oper. Res., vol. 4, p. 233–235, 1979. [GAM 97] GAMBOSI G., PROTASI M., TALAMO M., “Preserving approximation in the min- weighted Set Cover Problem”, Discrete Appl. Math., vol. 73, p. 13–22, 1997. [HOC 82] HOCHBAUM D. S., “Approximation algorithms for the set covering and vertex cover problems”, SIAM J. Comput., vol. 11, num. 3, p. 555–556, 1982. [JOH 74] J OHNSON D. S., “Approximation algorithms for combinatorial problems”, J. Com- put. System Sci., vol. 9, p. 256–278, 1974. [KAR 72] KARP R. M., “Reducibility among combinatorial problems”, MILLER R. E., THATCHER J. W., Eds., Complexity of computer computations, p. 85–103, Plenum Press, New York, 1972. [LOV 75] LOVÁSZ L., “On the ratio of optimal integral and fractional covers”, Discrete Math., vol. 13, p. 383–390, 1975. [PAS 97] PASCHOS V. T., “A survey about how optimal solutions to some covering and pack- ing problems can be approximated”, ACM Comput. Surveys, vol. 29, num. 2, p. 171–209, 1997. [RAZ 97] RAZ R., SAFRA S., “A sub-constant error probability low-degree test and a sub- constant error probability PCP characterization of NP”, Proc. STOC’97, p. 475–484, 1997. [SLA 96] SLAVÍK P., “A tight analysis of the greedy algorithm for set cover”, Proc. STOC’96, p. 435–441, 1996. [SLE 85] SLEATOR D., TARJAN R. E., “Amortized efficiency of list update and paging rules”, Commun. ACM, vol. 28, num. 2, p. 202–208, 1985. [TEL 04] TELELIS O. A., ZISSIMOPOULOS V., Dynamic maintenance of approximate set covers, Manuscript, 2004.
eBook - ePubNetwork and Discrete Location
Models, Algorithms, and Applications
- Mark S. Daskin(Author)
- 2013(Publication Date)
- Wiley(Publisher)
The second issue that must be faced in implementing this approach to solving integer programming problems is that of selecting the noninteger decision variable for branching at each node. Often, we select the variable whose value is closest to being an integer. More sophisticated rules that exploit the structure of the problem can and should be developed for specific problem contexts.Before leaving this section on the set covering model, we present the solution to the example problem for a range of coverage distances in Table 4.1 and Figure 4.5 . Note that the number of required facilities decreases in a step-function manner as the coverage distance increases. Figures such as that shown in Figure 4.5 will be very important as we solve center problems (as discussed in Chapter 5).Figure 4.5 Graph of solution to the set covering problem for the network of Figure 4.2 for various distances.Table 4.1 Solution to the Set Covering Problem for the Network of Figure 4.2 for Various Coverage Distances.
Note that facilities are constrained to be on the nodes in the solutions outlined above.Coverage Distance Locations Number Less than 7 A , B , C , D , E , F 6 7 A , B , C , E , F 5 8 B , C , E , F 4 9, 10 B , E , F 3 11–18 C , D 2 19 or more C 1 4.3 Applications of the Set Covering Model
The set covering problem has been applied in a broad range of contexts. In this section we outline a number of applications of the set covering model to problems outside the scope of location analysis. In Section 4.4, we summarize a number of extensions of the location set covering model that allow the model to incorporate additional (secondary) location concerns.Applications of the set covering model range from airline crew scheduling (Desrochers et al., 1991) to tool selection in flexible manufacturing systems (Daskin, Jones, and Lowe, 1990). In airline crew scheduling problems, we are given a set of flight legs I
eBook - PDFOperations Planning
Mixed Integer Optimization Models
- Joseph Geunes(Author)
- 2014(Publication Date)
- CRC Press(Publisher)
Taking this a step further, if we remove the requirement that the selected subsets must be disjoint (but retain the requirement that each of the original items must be included in at least one selected subset), then we have a so-called covering problem. In this version of the problem, the solution must be such that each item is allocated to (or covered by) at least one resource. This chapter discusses this class of covering, packing, and partitioning problems, for which numerous applications exist in operations contexts. For example, the set of items may correspond to production jobs, package deliv-eries, or customers, while the resources may correspond to production lines or machines, delivery vehicles, or service facilities. While, in general, this prob-lem class may consider non-identical resources, we will restrict our analysis in this chapter to situations in which the multiple available resources are iden-25 26 Operations Planning: Mixed Integer Optimization Models tical, and therefore the value or cost associated with a subset of items does not depend on the resource to which the subset is allocated (in principle, the set covering, packing, and partitioning problems we discuss in this chapter do not require explicitly defined resources, and the value or cost of a subset may depend only on the collection of items in the subset; in operations settings, we often have in mind a set of identical resources, such as machines, vehicles, or facilities to which a subset of items will be allocated). The following chap-ter on the generalized assignment problem (GAP) considers a particular type of set partitioning problem in which an item’s cost and/or resource capacity consumption may depend on the resource to which the item is assigned.
eBook - PDF- Armen S. Asratian, Tristan M. J. Denley, Roland Häggkvist(Authors)
- 1998(Publication Date)
- Cambridge University Press(Publisher)
Chapter 10 Coverings 10-1 Some examples of covering problems JVlany problems in graph theory can be formulated as an instance of the following, somewhat general, covering problem: We are given two sets X and Y, and with each element x € X there is an associated subset K(x) of elements of Y (which are covered in some sense by the element x). We know that U xeX K( x ) = Y> our task is to find a subset XQ C X of mini- mum cardinality such that {J xe x 0 K( x ) = Y"• The set X is called the covering set and the set Y is the covered set Every subset X f C X satisfying \J x£X f K( x ) = Y ls c&Ued a covering of Y by X. Our problem is to find a covering consisting of as few elements as possible, a minimum covering of F by X. As an example we might take X to be the set of all matchings in a bipartite graph G, 7 to be the set of edges E{G), and K(M) = M for each matching M e X. Then a proper A(G)- colouring of G induces a minimum covering of Y by X. There are many other possible such examples, several are given in the exercises for this section. Later, in Section 12.2, we will consider covering the edges of a non-bipartite graph with bipartite subgraphs with prescribed properties. First, however, there are several special forms of coverings for bipartite graphs which merit particular attention. So let G be a bipartite graph with bipartition (Vi, V2) without isolated vertices. Problem 1 (A minimum covering of V2 by Vi) Here the covering set X is the vertex set Vi, the covered set is V2, and K{x) = NG(X) for each a: € Vi. It is necessary to find a subset XQ C VI of minimum cardinality such that NG(XO) = V2. 174 175 10.1 Some examples of covering problems Example A museum wants to employ a number of interpreters to give tours in a number of different languages. How can the museum employ as few of the job applicants as possible, whilst still being able to offer tours in all the languages? This problem is easily reformulated as an instance of Problem 1.
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
