Covering problems: Difference between revisions

Revision as of 16:28, 11 March 2009

Revision as of 16:34, 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>

Line 19:

==References==

* {{Cite book | last=V. Vazirani | first=Vijay | authorlink=Vijay Vazirani | coauthors= | title=Approximation Algorithms | dateyear=2001 | publisher=Springer-Verlag | ___location= | isbn=3-540-65367-8 | pages=}}

[[Category:Combinatorics]]