Geodesic
Approximation of optima of integer programs of the packing--covering type
Diskretnaya Matematika, Tome 12 (2000) no. 1, pp. 96-106

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DM_2000_12_1_a7,
     author = {A. S. Asratyan and N. N. Kuzyurin},
     title = {Approximation of optima of integer programs of the packing--covering type},
     journal = {Diskretnaya Matematika},
     pages = {96--106},
     publisher = {mathdoc},
     volume = {12},
     number = {1},
     year = {2000},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2000_12_1_a7/}
}
TY  - JOUR
AU  - A. S. Asratyan
AU  - N. N. Kuzyurin
TI  - Approximation of optima of integer programs of the packing--covering type
JO  - Diskretnaya Matematika
PY  - 2000
SP  - 96
EP  - 106
VL  - 12
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2000_12_1_a7/
LA  - ru
ID  - DM_2000_12_1_a7
ER  - 
%0 Journal Article
%A A. S. Asratyan
%A N. N. Kuzyurin
%T Approximation of optima of integer programs of the packing--covering type
%J Diskretnaya Matematika
%D 2000
%P 96-106
%V 12
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2000_12_1_a7/
%G ru
%F DM_2000_12_1_a7
A. S. Asratyan; N. N. Kuzyurin. Approximation of optima of integer programs of the packing--covering type. Diskretnaya Matematika, Tome 12 (2000) no. 1, pp. 96-106. http://geodesic.mathdoc.fr/item/DM_2000_12_1_a7/