Analysis of the accuracy of randomized rounding for integer linear programming problems

We use randomised rounding to obtain an upper bound for the optimum value of the program
$$ \{\min\mathbf{cx}\mid A\mathbf x\geq\mathbf b,\mathbf x\geq\mathbf0,\ \mathbf x \text{ is an integer vector}\}, $$
where $\mathbf b>0$, $\mathbf c\geq0$ 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).
The first and the second authors were supported, respectively, by the Royal Swedish Academy of Sciences and the Russian Foundation for Basic Research, grants 02–01–00713 and 04–01–00359.