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:
“In 1869 he started his work for temperance instigated by three drunken men who came to his home with a paper signed by a saloonkeeper and his patrons on which was written “For God’s sake organize a temperance society.””
—Federal Writers’ Project Of The Wor, U.S. public relief program (1935-1943)
“Art is an experience, not the formulation of a problem.”
—Lindsay Anderson (b. 1923)