# The Stony Brook Algorithm Repository

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