Content deleted Content added
m added covering-packing info box |
|||
Line 3:
Important covering problems are the [[Set cover problem]], which is equivalent to the [[Hitting set|Hitting Set Problem]], and its special cases, the [[Vertex cover problem]] and the [[Edge cover problem]]. The set cover problem is dual to the [[set packing|set packing problem]].
{{Covering-Packing_Problem_Pairs}}
==LP Formulation==
In the context of [[linear programming]], one can think of any linear program as a covering problem if the coefficients in the constraint matrix, the objective function, and right-hand side are nonnegative.<ref>{{harvtxt|V. Vazirani|2001}}</ref> Let <math>\mathbf{b},\mathbf{c}</math> be vectors and <math>A</math> be a matrix, all with no negative entries. Then one can see the following [[integer linear program]] as the most general covering problem:
| |||