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)
“Whoever wants to set a good example must add a grain of foolishness to his virtue: then others can imitate and yet at the same time surpass the one they imitate—which human beings love to do.”
—Friedrich Nietzsche (1844–1900)
“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)