Geodesic
Load balancing in solving problems based on estimates of the computational complexity of subproblems
Informacionnye tehnologii i vyčislitelnye sistemy, no. 1 (2015), pp. 10-18

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

We proposed a new static load distribution strategy for parallel Branch-and-Bound method based on complexity estimates of sub-problems appearing in a Branch-and-Bound tree. This strategy can be used on parallel systems with low connectivity where dynamic load balancing is problematic. The experimental results demonstrated the superiority of the proposed strategy over other three strategies under test. Based on these results we draw some conclusions about the duration of the first (serial) part of the algorithm and choice of a load distribution strategy.
Keywords: Branch-and-Bound, parallel computing, load balance, evaluation of the computational complexity of subtasks. 
@article{ITVS_2015_1_a1,
     author = {Bo Tian and M. A. Posypkin and I. Kh. Sigal},
     title = {Load balancing in solving problems based on estimates of the computational complexity of subproblems},
     journal = {Informacionnye tehnologii i vy\v{c}islitelnye sistemy},
     pages = {10--18},
     publisher = {mathdoc},
     number = {1},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ITVS_2015_1_a1/}
}
TY  - JOUR
AU  - Bo Tian
AU  - M. A. Posypkin
AU  - I. Kh. Sigal
TI  - Load balancing in solving problems based on estimates of the computational complexity of subproblems
JO  - Informacionnye tehnologii i vyčislitelnye sistemy
PY  - 2015
SP  - 10
EP  - 18
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ITVS_2015_1_a1/
LA  - ru
ID  - ITVS_2015_1_a1
ER  - 
%0 Journal Article
%A Bo Tian
%A M. A. Posypkin
%A I. Kh. Sigal
%T Load balancing in solving problems based on estimates of the computational complexity of subproblems
%J Informacionnye tehnologii i vyčislitelnye sistemy
%D 2015
%P 10-18
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ITVS_2015_1_a1/
%G ru
%F ITVS_2015_1_a1
Bo Tian; M. A. Posypkin; I. Kh. Sigal. Load balancing in solving problems based on estimates of the computational complexity of subproblems. Informacionnye tehnologii i vyčislitelnye sistemy, no. 1 (2015), pp. 10-18. http://geodesic.mathdoc.fr/item/ITVS_2015_1_a1/