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/

[1] Nigmatullin R. G., “Algoritm naiskoreishego spuska v zadache na pokrytie”, Trudy simpoziuma po priblizhennym algoritmam, Kiev, 1969, 36

[2] Kuzyurin N. N., “Asimptoticheski tochnyi polinomialnyi algoritm dlya odnogo klassa zadach lineinogo buleva programmirovaniya”, Tezisy dokl. 3-i Vsesoyuznoi shkoly “Diskretnaya optimizatsiya i kompyutery”, TsEMI, 1987, 129

[3] Kuzyurin N. N., “Asimptoticheski tochnyi polinomialnyi algoritm v tselochislennom lineinom programmirovanii”, Diskretnaya matematika, 1:2 (1989), 79–85 | MR

[4] Sapozhenko A. A., “Ob odnom dokazatelstve verkhnei otsenki slozhnosti minimalnoi dnf dlya pochti vsekh funktsii”, Tezisy dokladov I Vsesoyuznoi konferentsii po problemam teoreticheskoi kibernetiki, Novosibirsk, 1969, 103

[5] Sapozhenko A. A., “O slozhnosti dnf, poluchaemykh s pomoschyu gradientnogo algoritma”, Diskretnyi analiz, no. 5, 1972, 111–116

[6] Khachiyan L. G., “Polinomialnyi algoritm v lineinom programmirovanii”, Dokl. AN SSSR, 244 (1979), 1093–1096 | MR | Zbl

[7] Bertsimas D., Vohra R., “Rounding algorithms for covering problems”, Math. Programming, 80 (1998), 63–89 | MR | Zbl

[8] Chvatal V., “A greedy heuristic for the set-covering problem”, Math. Oper. Res., 4 (1979), 233–235 | DOI | MR | Zbl

[9] Ford L. R., Fulkerson D. R., Flows in networks, Princeton Univ. Press, Princeton, 1962 | MR | Zbl

[10] Karmarkar N., “A new polynomial-time algorithm for linear programming”, Combinatorica, 4 (1984), 373–395 | DOI | MR | Zbl

[11] Kuzjurin N., “Generalized covers and their approximations”, EuroComb'03–Abstr, Prague, 2003, 247–250

[12] Lovasz L., “On the ratio of optimal integral and fractional covers”, Discrete Math., 13 (1975), 383–390 | DOI | MR | Zbl

[13] Motwani R., Raghavan P., Randomized algorithms, Cambridge Univ. Press, Cambridge, 1995 | MR | Zbl

[14] Raghavan P., Tompson C. D., “Randomized rounding: a technique for provably good algorithms and algorithmic proofs”, Combinatorica, 37 (1987), 365–374 | DOI | MR

[15] Rajagopalan S., Vazirani V. V., “Primal-dual (RNC) approximation algorithms for set cover and covering integer programs”, SIAM J. Comput., 28 (1999), 525–540 | DOI | MR

[16] Schrijver A., Theory of linear and integer programming, Wiley, New York, 1999 | MR

[17] Srinivasan A., “Improved approximations of packing and covering problems”, SIAM J. Comput., 29 (1999), 648–670 | DOI | MR | Zbl