Integer Linear Program Formulation
The minimum set cover problem can be formulated as the following integer linear program (ILP).
| minimize | (minimize the total cost) | ||
| subject to | for all | (cover every element of the universe) | |
| for all . | (every set is either in the set cover or not) |
This ILP belongs to the more general class of ILPs for covering problems. The integrality gap of this ILP is at most, so its relaxation gives a factor- approximation algorithm for the minimum set cover problem (where is the size of the universe).
Read more about this topic: Set Cover Problem
Famous quotes containing the words program and/or formulation:
“The actions of each dancer were scrutinized with great care and any little mistake noted and remembered. The strain upon a dancer was consequently so great that when a fine dancer died soon after a feast it was said, “The peoples’ looks have killed him.””
—Merle Colby, U.S. public relief program (1935-1943)
“In necessary things, unity; in disputed things, liberty; in all things, charity.”
—Variously Ascribed.
The formulation was used as a motto by the English Nonconformist clergyman Richard Baxter (1615-1691)