The paper explores the following question: suppose an Integer program ( min c*x Ax >= b, x in {0,1}) has integrality gap a, where A
is a 0,1 matrix, can one say anything about the "capacitated" version of the IP where each column of A is multiplied by an arbitrary positive integer? That is, is there a relation between a
covering problem (say covering a line using intervals) with a version where each element has a demand and each set has a supply. We answer a "conditional" yes: we define a related
0,1-optimization problem called the priority version, and if the priority version has integrality gap b, the capacitated version has an O(a+b) algorithm.
It would've been nice if b was O(a), and indeed we show in some problems that is the case, but this paper dashed that hope for general covering IPs.