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:
“These native villages are as unchanging as the woman in one of their stories. When she was called before a local justice he asked her age. “I have 45 years.” “But,” said the justice, “you were forty-five when you appeared before me two years ago.” “Señor Judge,” she replied proudly, drawing herself to her full height, “I am not of those who are one thing today and another tomorrow!””
—State of New Mexico, U.S. public relief program (1935-1943)
“You do not mean by mystery what a Catholic does. You mean an interesting uncertainty: the uncertainty ceasing interest ceases also.... But a Catholic by mystery means an incomprehensible certainty: without certainty, without formulation there is no interest;... the clearer the formulation the greater the interest.”
—Gerard Manley Hopkins (1844–1889)