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:
“When I saw it I was so glad I could not speak. My eyes seemed too little to see it all.... I was a long time without speaking to my friend. To see me always looking and never speaking he thought I had lost my mind. I could not understand where all this could come from.”
—For the State of Maine, 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)