The scalability analysis of a parallel tree search algorithm

DOI10.1007/S11590-020-01547-6MaRDI QIDQ5919087zbMATH OpenOpenAlexFDO

Authors Roman Kolpakov, M. A. Posypkin

Publication date 17 February 2021

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11590-020-01547-6

zbMATH Keywords

complexity analysisglobal optimizationparallel efficiencyparallel scalabilityparallel tree search

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Analysis of algorithms (68W40) Nonconvex programming, global optimization (90C26) Applications of mathematical programming (90C90)

Review text

The present paper deals with the scalability analysis associated with a parallel tree search algorithm. Moreover, there is shown that this parallel algorithm is close to the theoretical maximum.

Recommendations

• The scalability analysis of a parallel tree search algorithm
• scientific article; zbMATH DE number 934532
• scientific article; zbMATH DE number 2087981
• Scalability and parallelization of Monte-Carlo tree search
• Parallel depth first search. II: Analysis

Cites work

• A parallel branch and bound algorithm for the quadratic assignment problem
• Approximating a solution set of nonlinear inequalities
• Branch-and-Bound interval global optimization on shared memory multiprocessors
• Estimating the computational complexity of one variant of parallel realization of the branch-and-bound method for the knapsack problem
• Estimating the Efficiency of Backtrack Programs
• Global multidimensional optimization on parallel computer
• Global optimization: Fractal approach and non-redundant parallelism
• scientific article; zbMATH DE number 1971078 (Why is no real title available?)
• On a lower bound on the computational complexity of a parallel implementation of the branch-and-bound method
• Parallel global optimization on GPU
• Randomized parallel algorithms for backtrack search and branch-and-bound computation
• Sequential and parallel algorithms for global minimizing functions with Lipschitzian derivatives
• The scalability analysis of a parallel tree search algorithm
• Tight Bounds for On-Line Tree Embeddings
• Upper and lower bounds for the complexity of the branch and bound method for the knapsack problem

Cited in

(9)

• Parallel depth first search. I: Implementation
• Evaluation of a simple, scalable, parallel best-first search strategy
• scientific article; zbMATH DE number 3907763 (Why is no real title available?)
• On the scalability of PSRS algorithm
• scientific article; zbMATH DE number 2087981 (Why is no real title available?)
• scientific article; zbMATH DE number 934532 (Why is no real title available?)
• Анализ сложности алгоритма параллельного поиска “золотой” коллизии
• The scalability analysis of a parallel tree search algorithm
• The comparing analysis of two parallelization schemes for computations with round memory

This page was built for publication: The scalability analysis of a parallel tree search algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5919087)