# Difference between revisions of "Set covering problem"

Jump to navigation
Jump to search

Khaledfahat (talk | contribs) |
(Added a brief description of the problem) |
||

Line 1: | Line 1: | ||

Authors: Sherry Liang, Khalid Alanazi, Kumail Al Hamoud | 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.<span style="font-size: 8pt; position:relative; bottom: 0.3em;">1</span> | ||

== Introduction == | == Introduction == | ||

Line 25: | Line 27: | ||

== References == | == 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 |

## Revision as of 15:12, 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

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