Geodesic
On the best choice of a~branching variable in the subset sum problem
Diskretnaya Matematika, Tome 29 (2017) no. 1, pp. 51-58

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

The paper is concerned with estimating the computational complexity of the branch-and-bound method for the subset sum problem. We study the relationship between the way of decomposition of subproblems and the number of the method steps. The standard variant of the branch-and-bound method for the subset sum problem with binary branching is considered: any subproblem is decomposed into two more simple subproblems by assigning values $0$ and $1$ to a selected branching variable. It is shown that for any set of parameters of the problem the procedure of branching variables selection in the descending order of their weights is optimal.
Keywords: the branch-and-bound method, computational complexity, the subset sum problem. 
@article{DM_2017_29_1_a4,
     author = {R. M. Kolpakov and M. A. Posypkin},
     title = {On the best choice of a~branching variable in the subset sum problem},
     journal = {Diskretnaya Matematika},
     pages = {51--58},
     publisher = {mathdoc},
     volume = {29},
     number = {1},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2017_29_1_a4/}
}
TY  - JOUR
AU  - R. M. Kolpakov
AU  - M. A. Posypkin
TI  - On the best choice of a~branching variable in the subset sum problem
JO  - Diskretnaya Matematika
PY  - 2017
SP  - 51
EP  - 58
VL  - 29
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2017_29_1_a4/
LA  - ru
ID  - DM_2017_29_1_a4
ER  - 
%0 Journal Article
%A R. M. Kolpakov
%A M. A. Posypkin
%T On the best choice of a~branching variable in the subset sum problem
%J Diskretnaya Matematika
%D 2017
%P 51-58
%V 29
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2017_29_1_a4/
%G ru
%F DM_2017_29_1_a4
R. M. Kolpakov; M. A. Posypkin. On the best choice of a~branching variable in the subset sum problem. Diskretnaya Matematika, Tome 29 (2017) no. 1, pp. 51-58. http://geodesic.mathdoc.fr/item/DM_2017_29_1_a4/