Hitting Set Formulation
Set covering is equivalent to the hitting set problem. It is easy to see this by observing that an instance of set covering can be viewed as an arbitrary bipartite graph, with sets represented by vertices on the left, the universe represented by vertices on the right, and edges representing the inclusion of elements in sets. The task is then to find a minimum cardinality subset of left-vertices which covers all of the right-vertices. In the Hitting set problem, the objective is to cover the left-vertices using a minimum subset of the right vertices. Converting from one problem to the other is therefore achieved by interchanging the two sets of vertices.
Read more about this topic: Set Cover Problem
Famous quotes containing the words hitting, set and/or formulation:
“The fall into the abyss of deconstruction inspires us with as much pleasure as fear. We are intoxicated with the prospect of never hitting bottom.”
—Gayatri Chakravorty Spivak (b. 1942)
“He set the jug down slowly at his feet
With trembling care, knowing that most things break;”
—Edwin Arlington Robinson (1869–1935)
“Art is an experience, not the formulation of a problem.”
—Lindsay Anderson (b. 1923)