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/

[1] Kuzyurin N. N., “Asimptoticheski tochnye polinomialnye algoritmy v tselochislennom lineinom programmirovanii”, Diskretnaya matematika, 1:2 (1989), 78–85 | MR | Zbl

[2] Kuzyurin N. N., “Ob otnoshenii optimumov lineinykh i tselochislennykh programm”, Diskretnaya matematika, 3:1 (1991), 98–104 | MR

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

[4] Aharoni R., Erdős P., Linial N., “Primal and dual integer programs and the relationship between their optima”, Proc. 17th Annual ACM Symposium on Theory of Computing, 1985, 476–483

[5] Aharoni R., Erdős P., Linial N., “Optima of dual integer linear programs”, Combinatorica, 8:1 (1988), 476–483 | DOI | MR

[6] Awerbuch B., Azar Y., “Local optimization of global objectives: competitive distributed deadlock resolution and resource allocation”, Proc. 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, 240–249

[7] Bartal Y., Byers J. H., Raz D., “Global optimization using local information with applications to flow control”, Proc. 38th Annual IEEE Symposium on Foundations of Computer Science, 1997, 303–312

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

[9] Luby M., Nisan N., “A parallel approximation algorithm for positive linear programming”, Proc. 25th Annual Symposium on Theory of Computing, 1993, 448–457

[10] Motwani R., Raghavan P., Randomized Algorithms, Cambridge Univ. Press, Cambridge, 1995 | MR

[11] Papadimitriou C.H., Yannakakis M., “Linear programming without the matrix”, Proc. Annual ACM Symposium on Theory of Computing, 1993, 121–129 | MR

[12] Plotkin S., Shmoys D., Tardos E., “Fast approximation algorithms for fractional packing and covering problems”, Math. Oper. Research, 20 (1995), 257–301 | DOI | MR | Zbl

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

[14] Raghavan P., “Probabilistic construction of deterministic algorithms: approximating packing integer programs”, J. Comp. Syst. Sci., 37 (1988), 130–143 | DOI | MR | Zbl

[15] Schrijver A., Theory of Linear and Integer Programming, Wiley, New York, 1986 | MR | Zbl

[16] Spencer J., Ten Lectures on the Probabilistic Method, SIAM, Philadelphia, 1987 | MR

[17] Srinivasan A., “Improved approximations of packing and covering problems”, Proc. ACM Symposium on Theory of Computing, 1995, 268–276 | Zbl

[18] Srivastav A., Stangier P., “Algorithmic Chernoff–Hoeffding inequalities in integer programming”, Random Structures and Algorithms, 8, no. 1, 1996, 27–58 | MR | Zbl