Geodesic
Effective parallelization strategy for the solution of subset sum problems by the branch-and-bound method
Diskretnaya Matematika, Tome 31 (2019) no. 4, pp. 20-37
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

An easily implementable recursive parallelization strategy for solving the subset sum problem by the branch-and-bound method is proposed. Two different frontal and balanced variants of this strategy are compared. On an example of a particular case of the subset sum problem we show that the balanced variant is more effective than the frontal one. Moreover, we show that, for the considered particular case of the subset sum problem, the balanced variant is also time optimal.
Keywords: the branch-and-bound method, parallel computational complexity, the subset sum problem. 
@article{DM_2019_31_4_a1,
     author = {R. M. Kolpakov and M. A. Posypkin},
     title = {Effective parallelization strategy for the solution of subset sum problems by the branch-and-bound method},
     journal = {Diskretnaya Matematika},
     pages = {20--37},
     year = {2019},
     volume = {31},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2019_31_4_a1/}
}
TY  - JOUR
AU  - R. M. Kolpakov
AU  - M. A. Posypkin
TI  - Effective parallelization strategy for the solution of subset sum problems by the branch-and-bound method
JO  - Diskretnaya Matematika
PY  - 2019
SP  - 20
EP  - 37
VL  - 31
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DM_2019_31_4_a1/
LA  - ru
ID  - DM_2019_31_4_a1
ER  - 
%0 Journal Article
%A R. M. Kolpakov
%A M. A. Posypkin
%T Effective parallelization strategy for the solution of subset sum problems by the branch-and-bound method
%J Diskretnaya Matematika
%D 2019
%P 20-37
%V 31
%N 4
%U http://geodesic.mathdoc.fr/item/DM_2019_31_4_a1/
%G ru
%F DM_2019_31_4_a1
R. M. Kolpakov; M. A. Posypkin. Effective parallelization strategy for the solution of subset sum problems by the branch-and-bound method. Diskretnaya Matematika, Tome 31 (2019) no. 4, pp. 20-37. http://geodesic.mathdoc.fr/item/DM_2019_31_4_a1/

[1] Martello S., Toth P., Knapsack Problems, John Wiley Sons Ltd, Chichester, England, 1990, 296 pp. | MR | Zbl

[2] Kellerer H., Pfershy U., Pisinger D., Knapsack Problems, Springer Verlag, Berlin Heidelberg, 2004, 548 pp. | MR | Zbl

[3] Kolpakov R. M., Posypkin M. A., “On the best choice of a branching variable in the subset sum problem”, Discrete Math. Appl., 28:1 (2018), 29–34 | DOI | DOI | MR | MR | Zbl

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

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

[6] Kolpakov R. M., Posypkin M. A., “Upper and lower bounds for the complexity of the branch and bound method for the knapsack problem”, Discrete Math. Appl., 20:1 (2010), 95–112 | DOI | DOI | MR | Zbl

[7] Bhatt S.N., Greenberg D., Leighton F.T., Liu P., “Tight bounds for on-line tree embeddings”, SIAM J. Comput., 29:2 (1999), 474–491 | DOI | MR

[8] Herley K.T., Pietracaprina A., Pucci G., “Deterministic parallel backtrack search”, Theor. Comput. Sci., 270 (2002), 309–324 | DOI | MR | Zbl

[9] Karp R.M., Zhang Y., “Parallel algorithms for backtrack search and branch and bound computation”, J. ACM, 40:3 (1993), 765–789 | DOI | MR | Zbl

[10] Pietracaprina A., Pucci G., Silvestri F., Vandin F., “Space-efficient parallel algorithms for combinatorial search problems”, J. Paral. Distrib. Comput., 76 (2015), 58–65 | DOI | MR

[11] Wu I.C., Kung H.T., “Communication complexity for parallel divide-and-conquer”, Proc. 32nd IEEE Symp. Found. Comput. Sci., 1991, 151–162 | MR