Covering problems: Difference between revisions

Revision as of 16:34, 11 March 2009

Revision as of 16:35, 11 March 2009

Line 5:

==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:

: minimize <math>\mathbf{c}^T \mathbf{x}</math>