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:
“It is not [the toddler’s] job yet to consider other people’s feelings, he has to come to terms with his own first. If he hits you and you hit him back to “show him what it feels like,” you will have given a lesson he is not ready to learn. He will wail as if hitting was a totally new idea to him. He makes no connections between what he did to you and what you then did to him; between your feelings and his own.”
—Penelope Leach (20th century)
“I do not set my life at a pin’s fee,
And for my soul, what can it do to that,
Being a thing immortal as itself?”
—William Shakespeare (1564–1616)
“In necessary things, unity; in disputed things, liberty; in all things, charity.”
—Variously Ascribed.
The formulation was used as a motto by the English Nonconformist clergyman Richard Baxter (1615-1691)