Showing a limited preview of this publication:
We use randomised rounding to obtain an upper bound for the optimum value of the program
{min cx | Ax ≥ b, x ≥ 0, x is an integer vector},
where b > 0, c ≥ 0 are rational vectors and A is an arbitrary rational matrix. Our bound generalises some known bounds for covering integer programs (that is, the same programs with the restriction that all elements of A are non-negative).
Published Online: 2004-10-01
Published in Print: 2004-10-01
Copyright 2004, Walter de Gruyter