Set Cover Problem

3 Key excerpts on "Set Cover Problem"

• 

  eBook - ePub

  An Elementary Approach to Design and Analysis of Algorithms

  • Lekh Raj Vermani, Shalini Vermani(Authors)
  • 2019(Publication Date)
  • WSPC (EUROPE)

    (Publisher)

  Example 15.3. Let S be a finite set and F a family of non-empty subsets S

  i

  of S such that S = S

  i

  . A subfamily F′ of F is called a (set) cover of S if S = S

  i

  .

  Set Cover Problem (or SC in short) is to find a smallest subfamily F′ of F which covers S.

  The corresponding (or equivalent) decision problem states:

  Given a finite set S, a family F of non-empty subsets S

  i

  of S with S = S

  i

  and a positive integer k, does there exist a subfamily F′ of F with |F′| ≤ k which covers S?

  Example 15.4. Let a graph G = (V, E) be given. A subset S of V is called an independent set of G if whenever u, v ∈ S, then there is no edge in G between u and v.

  Independent Set Problem is then to find the largest independent subset of G.

  Equivalent decision version of this problem says:

  Given a graph G and a positive integer k, does there exist an independent set in G with at least k elements?

  Example 15.5. Let G = (V, E) be a graph. A subset C of V is called a clique in G if every two vertices in C are adjacent in G. Alternatively a clique in G is a complete subgraph of G.

  The k-clique problem in G is to find a clique in G with k vertices. Sometimes the clique problem may also be stated as to find a largest clique in G. As a decision problem it says the following:

  Given a graph G = (V, E) and a positive integer k, does there exist a clique in G with at least k vertices?

  15.3.Reducibility or Reductions

  For studying NP-completeness of problems, we need an important concept of reducibility of problems.

  Definition. Let X and Y be two decision problems with Q

  X

  and Q

  Y

  the questions of the problems X and Y, respectively. Let A be a polynomial time algorithm that maps an instance I

  X

  of X onto an instance I

  Y

  of Y. If the answer of Q

  X

  for I

  X

  equals the answer of Q

  Y

  for I

  Y

  then the algorithm A is called a transform that transforms X to Y

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Handbook of Approximation Algorithms and Metaheuristics

  Contemporary and Emerging Applications, Volume 2

  • Teofilo F. Gonzalez, Teofilo F. Gonzalez(Authors)
  • 2018(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Lecture Notes on Computer Science, 4508, 317, 2007.

  9 .  Bronnimann, H., Goodrich, M. T., Almost optimal set covers in finite vc-dimension, Discrete and Computational Geometry, 14, 463, 1995.

  10 .  Gandhi, R., Khuller, S., Srinivasan, A., Approximation algorithms for partial covering problems, Journal of Algorithms, 53, 55, 2004.

  11 .  Agarwal, P.K., Procopiuc, C.M., Exact and approximation algorithms for clustering, Algorithmica, 33, 201, 2002.

  12 .  Khuller, S., Moss, A., Naor, J.S., The budgeted maximum coverage problem, Information Processing Letters, 70, 39, 1999.

  13 .  Chazelle, B.M., Lee, D.T., On a circle placement problem, Computing, 36, 1, 1986.

  14 .  Berg, M.D., Cabello, S., Har-Peled, S., Covering many or few points with unit disks, Theory of Computing Systems, 45, 446, 2009.

  15 .  Ghasemalizadeh, H., Razzazi, M., An improved approximation algorithm for the most points covering problem, Theory of Computing Systems, 50(3), 545, 2012.

  16 .  Shmoys, D.B., Tardos, É., Aardal, K., Approximation algorithms for facility location problems, Proceedings of 29th Annual Symposium on Theory of Computing, ACM, New York, pp. 265–274, 1997.

  17 .  Chuzhoy, J., Naor, J., Covering problems with hard capacities, SIAM Journal on Computing, 36(2), 498, 2006.

  18 .  Bar-Ilan, J., Kortsarz, G., Peleg, D., How to allocate network centers, Journal of Algorithms, 15, 385, 1993.

  19 .  Wolsey, L.A., An analysis of the greedy algorithm for the submodular set covering problem, Combinatorica, 2, 385, 1982.

  20 .  Khuller, S., Sussmann, Y., The capacitated k-center problem, SIAM Journal on Discrete Mathematics, 13, 403, 2000.

  21 .  Mahdian M., Ye Y., Zhang J., A 2-approximation algorithm for the soft-capacitated facility location problem, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Network 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.

  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

  Note that facilities are constrained to be on the nodes in the solutions outlined above.

  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

  Sign up to read

  Learn more about book