Editing Linear programming (section)

== Variations ==

=== Covering/packing dualities ===
<!--Linked from [[Template:Covering/packing-problem pairs]]-->
{{Covering/packing-problem pairs}}

A [[Covering problem|covering LP]] is a linear program of the form:
: Minimize:  <big>'''b'''<sup>T</sup>'''y'''</big>,
: subject to: <big>''A''<sup>T</sup>'''y''' ≥ '''c''', '''y''' ≥ 0</big>,
such that the matrix ''A'' and the vectors '''b''' and '''c''' are non-negative.

The dual of a covering LP is a [[Packing problem|packing LP]], a linear program of the form:
: Maximize: <big>'''c'''<sup>T</sup>'''x'''</big>,
: subject to: <big>''A'''''x''' ≤ '''b''', '''x''' ≥ 0</big>,
such that the matrix ''A'' and the vectors '''b''' and '''c''' are non-negative.

==== Examples ====
Covering and packing LPs commonly arise as a [[linear programming relaxation]] of a combinatorial problem and are important in the study of [[approximation algorithms]].<ref>{{harvtxt|Vazirani|2001|p=112}}</ref> For example, the LP relaxations of the [[Set packing|set packing problem]], the [[independent set problem]], and the [[Matching (graph theory)|matching problem]] are packing LPs. The LP relaxations of the [[set cover problem]], the [[vertex cover problem]], and the [[dominating set problem]] are also covering LPs.

Finding a [[fractional coloring]] of a [[Graph (discrete mathematics)|graph]] is another example of a covering LP. In this case, there is one constraint for each vertex of the graph and one variable for each [[Independent set (graph theory)|independent set]] of the graph.