Dual Integer Linear Programs and the Relationship between their Optima

We consider dual pairs of packing and covering integer linear programs. Best possible bounds are found between their optimal values. Tight inequalities are obtained relating the integral optima and the optimal rational solutions.

Authors

• Ron Aharoni
• Paul Erdös
• Nati Linial

Keywords

No keywords are indexed for this paper.