Geodesic
Analysis of the accuracy of randomized rounding for integer linear programming problems
Diskretnaya Matematika, Tome 16 (2004) no. 4, pp. 3-13

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

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. 
@article{DM_2004_16_4_a0,
     author = {A. S. Asratyan and N. N. Kuzyurin},
     title = {Analysis of the accuracy of randomized rounding for integer linear programming problems},
     journal = {Diskretnaya Matematika},
     pages = {3--13},
     publisher = {mathdoc},
     volume = {16},
     number = {4},
     year = {2004},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2004_16_4_a0/}
}
TY  - JOUR
AU  - A. S. Asratyan
AU  - N. N. Kuzyurin
TI  - Analysis of the accuracy of randomized rounding for integer linear programming problems
JO  - Diskretnaya Matematika
PY  - 2004
SP  - 3
EP  - 13
VL  - 16
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2004_16_4_a0/
LA  - ru
ID  - DM_2004_16_4_a0
ER  - 
%0 Journal Article
%A A. S. Asratyan
%A N. N. Kuzyurin
%T Analysis of the accuracy of randomized rounding for integer linear programming problems
%J Diskretnaya Matematika
%D 2004
%P 3-13
%V 16
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2004_16_4_a0/
%G ru
%F DM_2004_16_4_a0
A. S. Asratyan; N. N. Kuzyurin. Analysis of the accuracy of randomized rounding for integer linear programming problems. Diskretnaya Matematika, Tome 16 (2004) no. 4, pp. 3-13. http://geodesic.mathdoc.fr/item/DM_2004_16_4_a0/