Covering-Packing Dualities

Covering-Packing Dualities
Covering problems Packing problems
Minimum Set Cover Maximum Set Packing
Minimum Vertex Cover Maximum Matching
Minimum Edge Cover Maximum Independent Set

A covering LP is a linear program of the form

minimize \mathbf{b}^T \mathbf{y}
subject to  \mathbf{A}^T \mathbf{y} \ge \mathbf{c}, \, \mathbf{y} \ge 0

such that the matrix \mathbf{A} and the vectors \mathbf{b} and \mathbf{c} are non-negative.

The dual of a covering LP is a packing LP, a linear program of the form

maximize \mathbf{c^T}\mathbf{x}
subject to \mathbf{A}\mathbf{x} \le \mathbf{b}, \, \mathbf{x} \ge 0

such that the matrix \mathbf{A} and the vectors \mathbf{b} and \mathbf{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.[1] For example, the LP relaxations of the set packing problem, the independent set problem, and the matching problem are packing LPs. The LP relaxations of the set cover problem, the vertex cover problem, and the dominating set problem are covering LPs.

Finding a fractional coloring of a 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 of the graph.