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 toddler’s wish to please ... is a powerful aid in helping the child to develop a social awareness and, eventually, a moral conscience. The child’s love for the parent is so strong that it causes him to change his behavior: to refrain from hitting and biting, to share toys with a peer, to become toilet trained. This wish for approval is the parent’s most reliable ally in the process of socializing the child.”
—Alicia F. Lieberman (20th century)
“Greatness collapses of itself: such limit the gods have set to the growth of prosperous states.”
—Marcus Annaeus Lucan (39–65)
“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)