| 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: bTy,
- Subject to: ATy ≥ c, y ≥ 0,
such that the matrix A and the vectors b and c are non-negative.
The dual of a covering LP is a packing LP, a linear program of the form:
- Maximize: cTx,
- Subject to: Ax ≤ b, x ≥ 0,
such that the matrix A and the vectors b and c are non-negative.
Read more about this topic: Linear Programming