Approximation algorithms for covering/packing integer programs

This gives an O(lnm)-approximation algorithm for CIP-minimum-cost covering integer programs with multiplicity constraints, i.e., the special case when there are no packing constraints Bx⩽b. The previous best approximation ratio has been O(ln(maxj∑iAij)) since 1982. CIP contains the set cover problem as a special case, so O(lnm)-approximation is the best possible unless P=NP.