Geodesic
Bounds on average number of iterations of the algorithms for solving some Boolean programming problems
Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 3, pp. 49-64.

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

The paper is devoted to the polynomial upper bounds on average number of iterations for some integer linear programming algorithms for solving the multidimensional knapsack problem and the set packing problem. These results were obtained using earlier suggested approach. Expansions of the known classes of problems with similar bounds are described. Tab. 2, bibliogr. 19.
Keywords: average number of iterations, knapsack problem, set packing problem, Gomory cut, branch and bound algorithm, $L$-class enumeration. 
@article{DA_2011_18_3_a4,
     author = {L. A. Zaozerskaya and A. A. Kolokolov and N. G. Gofman},
     title = {Bounds on average number of iterations of the algorithms for solving some {Boolean} programming problems},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {49--64},
     publisher = {mathdoc},
     volume = {18},
     number = {3},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2011_18_3_a4/}
}
TY  - JOUR
AU  - L. A. Zaozerskaya
AU  - A. A. Kolokolov
AU  - N. G. Gofman
TI  - Bounds on average number of iterations of the algorithms for solving some Boolean programming problems
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2011
SP  - 49
EP  - 64
VL  - 18
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2011_18_3_a4/
LA  - ru
ID  - DA_2011_18_3_a4
ER  - 
%0 Journal Article
%A L. A. Zaozerskaya
%A A. A. Kolokolov
%A N. G. Gofman
%T Bounds on average number of iterations of the algorithms for solving some Boolean programming problems
%J Diskretnyj analiz i issledovanie operacij
%D 2011
%P 49-64
%V 18
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2011_18_3_a4/
%G ru
%F DA_2011_18_3_a4
L. A. Zaozerskaya; A. A. Kolokolov; N. G. Gofman. Bounds on average number of iterations of the algorithms for solving some Boolean programming problems. Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 3, pp. 49-64. http://geodesic.mathdoc.fr/item/DA_2011_18_3_a4/

[1] Gavrilov G. P., Sapozhenko A. A., Sbornik zadach po diskretnoi matematike, Nauka, M., 1977, 368 pp. | MR

[2] Grishukhin V. P., “O srednem chisle iteratsii algoritma Balasha”, Issledovaniya po diskretnoi matematike, Nauka, M., 1973, 58–68

[3] Geri M., Dzhonson M., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR

[4] Zaozërskaya L. A., Borisenko D. A., Gofman N. G., “O chisle dopustimykh reshenii zadachi ob upakovke mnozhestva”, Dinamika sistem, mekhanizmov i mashin, Materialy VII mezhdunar. nauchno-tekhnicheskoi konf., v. 3, Izdatelstvo OmGTU, Omsk., 2009, 31–35

[5] Zaozërskaya L. A., Kolokolov A. A., “O srednem chisle iteratsii nekotorykh algoritmov dlya resheniya zadachi ob upakovke mnozhestva”, Metody optimizatsii i ikh prilozheniya, Tr. XIV Baikalskoi mezhdunar. shkoly-seminara, v. 1, ISEM SO RAN, Irkutsk, 2008, 388–395

[6] Zaozërskaya L. A., Kolokolov A. A., “O srednem chisle iteratsii nekotorykh algoritmov dlya resheniya zadachi ob upakovke mnozhestva”, Zhurn. vychisl. matematiki i mat. fiziki, 50:2 (2010), 242–248 | MR | Zbl

[7] Kolokolov A A., “Regulyarnye razbieniya i otsecheniya v tselochislennom programmirovanii”, Sib. zhurn. issled. operatsii, 1:2 (1994), 18–39 | MR | Zbl

[8] Kolokolov A. A., Devyaterikova M. V., Zaozërskaya L. A., Regulyarnye razbieniya v tselochislennom programmirovanii, Uchebnoe posobie, Izd-vo OmGU, Omsk, 2007, 60 pp.

[9] Kuzyurin N. N., “Polinomialnyi v srednem algoritm v tselochislennom lineinom programmirovanii”, Sib. zhurn. issled. operatsii, 1:3 (1994), 38–48 | MR | Zbl

[10] Kuzyurin N. N., Fomin S. A., Effektivnye algoritmy i slozhnost vychislenii, 2008 http://discopal.ispras.ru/images/f/f4/Book-advanced-algorithms.pdf

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

[12] Khu T., Tselochislennoe programmirovanie i potoki v setyakh, Mir, M., 1974, 519 pp. | MR

[13] Beier R., Vöcking B., “Probabilistic analysis of knapsack core algorithms”, Proc. 15th Annual Symp. Discrete Algorithms (SODA-2004), SIAM, New Orleans, 2004, 468–477 | MR

[14] Brown C. A., Purdom P. W. (jr.), “An average time analysis of backtracking”, SIAM J. Comput., 10:3 (1981), 583–593 | DOI | MR

[15] Dinh Dieu P., Cong Thang L., Tuan Hoa L., “Average polynomial time complexity of some NP-complete problems”, Theoret. Comput. Sci., 46:2 (1986), 219–237 | MR | Zbl

[16] Gurevitch Y., Shelah S., “Expected computation time for Hamiltonian path problem”, SIAM J. Comput., 16:3 (1987), 486–502 | DOI | MR

[17] Nemhauser G. L., Wolsey L. A., Integer and combinatorial optimization, Wiley-Intersci. Publ., John Wiley and Sons, Inc., New York–Chichester–Weinheim–Brisbane–Singapore–Toronto, 1999, 763 pp. | MR

[18] Iwama K., “CNF satisfiability test by counting and polynomial average time”, SIAM J. Comput., 18:2 (1989), 385–391 | DOI | MR | Zbl

[19] Smale S., “On the average number of steps of the simplex method of linear programming”, Math. Programming, 27:3 (1983), 241–262 | DOI | MR