Speedup estimates for some variants of the parallel implementations of the branch-and-bound method
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 46 (2006) no. 12, pp. 2289-2304
Voir la notice de l'article provenant de la source Math-Net.Ru
The efficiency of parallel implementations of the branch-and-bound method in discrete optimization problems is considered. A theoretical analysis and comparison of two parallel implementations of this method is performed. A mathematical model of the computation process is constructed and used to obtain estimates of the maximum possible speedup. Examples of problems in which none of these two parallel implementations can speed up the computations are considered.
@article{ZVMMF_2006_46_12_a15,
author = {M. A. Posypkin and I. Kh. Sigal},
title = {Speedup estimates for some variants of the parallel implementations of the branch-and-bound method},
journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
pages = {2289--2304},
publisher = {mathdoc},
volume = {46},
number = {12},
year = {2006},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/ZVMMF_2006_46_12_a15/}
}
TY - JOUR AU - M. A. Posypkin AU - I. Kh. Sigal TI - Speedup estimates for some variants of the parallel implementations of the branch-and-bound method JO - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki PY - 2006 SP - 2289 EP - 2304 VL - 46 IS - 12 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/ZVMMF_2006_46_12_a15/ LA - ru ID - ZVMMF_2006_46_12_a15 ER -
%0 Journal Article %A M. A. Posypkin %A I. Kh. Sigal %T Speedup estimates for some variants of the parallel implementations of the branch-and-bound method %J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki %D 2006 %P 2289-2304 %V 46 %N 12 %I mathdoc %U http://geodesic.mathdoc.fr/item/ZVMMF_2006_46_12_a15/ %G ru %F ZVMMF_2006_46_12_a15
M. A. Posypkin; I. Kh. Sigal. Speedup estimates for some variants of the parallel implementations of the branch-and-bound method. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 46 (2006) no. 12, pp. 2289-2304. http://geodesic.mathdoc.fr/item/ZVMMF_2006_46_12_a15/