Set covering problem: Difference between revisions

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
(Added a brief description of the problem)
(Added some main applications)
Line 19: Line 19:
== Applications ==
== Applications ==


 
The applications of the set covering problem span a wide range of applications, but its usefulness is evident in industrial and governmental planning. Variations of the set covering problem that are of practical significance include the following.
 
;The optimal covering location problem
 
:This set covering problems is concerned with maximizing the population coverage of some public facility.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">2</span> Consider the problem of placing hospitals at different cities around some state.
;The cell tower coverage problem
:
;The airline crew scheduling problem
:
:
== Conclusion ==
== Conclusion ==



Revision as of 17:28, 21 November 2020

Authors: Sherry Liang, Khalid Alanazi, Kumail Al Hamoud

The set covering problem is a significant NP-hard problem in combinatorial optimization. In the set covering problem, two sets are given: a set S of elements and a set A of subsets of the set S. Each subset in A is associated with a predetermined cost, and the union of all the subsets covers the set S. This combinatorial problem then concerns finding the optimal number of subsets whose union covers the universal set while minimizing the total cost.1

Introduction

Methodology

Example

Applications

The applications of the set covering problem span a wide range of applications, but its usefulness is evident in industrial and governmental planning. Variations of the set covering problem that are of practical significance include the following.

The optimal covering location problem
This set covering problems is concerned with maximizing the population coverage of some public facility.2 Consider the problem of placing hospitals at different cities around some state.
The cell tower coverage problem
The airline crew scheduling problem

Conclusion

References

  1. Grossman, T., & Wool, A. (1997). Computational experience with approximation algorithms for the set covering problem. European Journal of Operational Research, 101(1), 81-92. doi:10.1016/s0377-2217(96)00161-0