# Difference between revisions of "Set covering problem"

(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 16: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

*of subsets of the set*

**A***. Each subset in*

**S***is associated with a predetermined cost, and the union of all the subsets covers the set*

**A***. This combinatorial problem then concerns finding the optimal number of subsets whose union covers the universal set while minimizing the total cost.1*

**S**## 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

- 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