# Set covering problem

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