Analysis of randomised rounding for integer programs
Albert Asratyan, Nikolai Nikolaevich Kuzyurin · Discrete Mathematics and Applications · 2004
We use randomised rounding to obtain an upper bound for the optimum value of the program {min cx | A x ≥ 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).