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:
“Resorts advertised for waitresses, specifying that they “must appear in short clothes or no engagement.” Below a Gospel Guide column headed, “Where our Local Divines Will Hang Out Tomorrow,” was an account of spirited gun play at the Bon Ton. In Jeff Winney’s California Concert Hall, patrons “bucked the tiger” under the watchful eye of Kitty Crawhurst, popular “lady” gambler.”
—Administration in the State of Colo, U.S. public relief program (1935-1943)
“Art is an experience, not the formulation of a problem.”
—Lindsay Anderson (b. 1923)