 # The Stony Brook Algorithm Repository

## 1.7.1 Set Cover   ## INPUT OUTPUT

Input Description: A set of subsets S_1, ..., S_m of the universal set U = \{1,...,n\}.

Problem: What is the smallest subset of subsets T \subset S such that \cup_{t_i \in T} t_i = U?

Excerpt from The Algorithm Design Manual: Set cover arises when you try to efficiently acquire or represent items that have been packaged in a fixed set of lots. You want to obtain all the items, while buying as few lots as possible. Finding a cover is easy, because you can always buy one of each lot. However, by finding a small set cover you can do the same job for less money.

An interesting application of set cover is Boolean logic minimization. We are given a particular Boolean function of k variables, which for each of the 2k possible input vectors describes whether the desired output is 0 or 1. We seek the simplest circuit that exactly implements this function. One approach is to find a disjunctive normal form (DNF) formula on the variables and their complements, such as x1 \bar x2 + \bar{x}1 \bar{x}2. We could build one and'' term for each input vector and then or'' them all together, but we might save considerably by factoring out common subsets of variables. Given a set of feasible and'' terms, each of which covers a subset of the vectors we need, we seek to or'' together the smallest number of terms that realize the function. This is exactly the set cover problem.

## Implementations

• Discrete Optimization Methods (Pascal) (rating 6)
• SYMPHONY: mixed-integer linear programming solver (C) (rating 6)

• ## Recommended Books Introduction to Algorithms by T. Cormen and C. Leiserson and R. Rivest and C. Stein Discrete Optimization Algorithms with Pascal Programs by M. Syslo and N. Deo and J. Kowalik Combinatorial Optimization: Algorithms and Complexity by C. Papadimitriou and K. Steiglitz

## Related Problems  Matching  Polygon Partitioning  Set Data Structures  Set Packing  Vertex Cover