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
- subject to
such that the matrix and the vectors and are non-negative.
The dual of a covering LP is a packing LP, a linear program of the form
- maximize
- subject to
such that the matrix and the vectors and 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.