Approximation of optima of integer programs of the packing–covering type

We consider the problem on estimating optima of the so-called packing–covering programs, which contain constrains of packing and covering types simultaneously. We introduce the notion of $\delta$-relaxation of such programs and show that the randomized rounding permits to obtain simple sufficient conditions for tight approximations of the integer-valued optima by the optima of the $\delta$-relaxations. We suggest an efficient randomized algorithm for finding an approximate solution of integer packing–covering linear integer programs and point out that this algorithm can be transformed to a deterministic algorithm by the well-known techniques of de-randomization.
The research was supported by the Swedish Institute and the Russian Foundation for Basic Research, grant 99–01–00210.