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:
“Can we not teach children, even as we protect them from victimization, that for them to become victimizers constitutes the greatest peril of all, specifically the sacrifice—physical or psychological—of the well-being of other people? And that destroying the life or safety of other people, through teasing, bullying, hitting or otherwise, “putting them down,” is as destructive to themselves as to their victims.”
—Lewis P. Lipsitt (20th century)
“Those who want to row on the ocean of human knowledge do not get far, and the storm drives those out of their course who set sail.”
—Franz Grillparzer (1791–1872)
“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)