Geodesic
Upper and lower bounds for the complexity of the branch and bound method for the knapsack problem
Diskretnaya Matematika, Tome 22 (2010) no. 1, pp. 58-73
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

This paper is devoted to questions concerning the complexity of solution of the problem on one-dimensional Boolean knapsack by the branch and bound method. For this complexity we obtain two upper bounds. We separate the special case of the knapsack problem where the complexity is polynomially bounded by the dimension of the problem. We also obtain an upper and lower bounds for the complexity of solution by the branch and bound method of the subset sum problem which is a special case of the knapsack problem. 
@article{DM_2010_22_1_a4,
     author = {R. M. Kolpakov and M. A. Posypkin},
     title = {Upper and lower bounds for the complexity of the branch and bound method for the knapsack problem},
     journal = {Diskretnaya Matematika},
     pages = {58--73},
     year = {2010},
     volume = {22},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2010_22_1_a4/}
}
TY  - JOUR
AU  - R. M. Kolpakov
AU  - M. A. Posypkin
TI  - Upper and lower bounds for the complexity of the branch and bound method for the knapsack problem
JO  - Diskretnaya Matematika
PY  - 2010
SP  - 58
EP  - 73
VL  - 22
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DM_2010_22_1_a4/
LA  - ru
ID  - DM_2010_22_1_a4
ER  - 
%0 Journal Article
%A R. M. Kolpakov
%A M. A. Posypkin
%T Upper and lower bounds for the complexity of the branch and bound method for the knapsack problem
%J Diskretnaya Matematika
%D 2010
%P 58-73
%V 22
%N 1
%U http://geodesic.mathdoc.fr/item/DM_2010_22_1_a4/
%G ru
%F DM_2010_22_1_a4
R. M. Kolpakov; M. A. Posypkin. Upper and lower bounds for the complexity of the branch and bound method for the knapsack problem. Diskretnaya Matematika, Tome 22 (2010) no. 1, pp. 58-73. http://geodesic.mathdoc.fr/item/DM_2010_22_1_a4/

[1] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, Moskva, 1986 | MR

[2] Kellerer H., Pferschy U., Pisinger D., Knapsack problems, Springer, Berlin, 2004 | MR | Zbl

[3] Martello S., Toth P., Knapsack problems, Wiley, New York, 1990 | MR | Zbl

[4] Kolesar P. J., “A branch and bound algorithm for the knapsack problem”, Management Sci., 13 (1967), 723–735 | DOI

[5] Greenberg H., Hegerich R. L., “A branch and bound algorithm for the knapsack problem”, Management Sci., 16 (1970), 327–332 | DOI | MR | Zbl

[6] Sigal I. Kh., Ivanova A. P., Vvedenie v prikladnoe diskretnoe programmirovanie, Fizmatlit, Moskva, 2002

[7] Grishukhin V. P., “Effektivnost metoda vetvei i granits v zadachakh s bulevymi peremennymi”, Issledovaniya po diskretnoi optimizatsii, Nauka, Moskva, 1976, 203–230

[8] Finkelshtein Yu. Yu., Priblizhennye metody i prikladnye zadachi diskretnogo programmirovaniya, Nauka, Moskva, 1976

[9] Kolpakov R. M., Posypkin M. A., Sigal I. Kh., “O slozhnosti resheniya zadachi o bulevom rantse”, Diskretnye modeli v teorii upravlyayuschikh sistem, MAKS Press, Moskva, 2006, 166–171