Space-Efficient Parallel Algorithms for Combinatorial Search Problems

DOI10.1007/978-3-642-40313-2_63MaRDI QIDQ2849956zbMATH OpenOpenAlexFDO

Authors Andrea Pietracaprina, Geppino Pucci, Francesco Silvestri, Fabio Vandin

Publication date 20 September 2013

Published in Mathematical Foundations of Computer Science 2013 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.2552

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Parallel algorithms in computer science (68W10) Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: We present space-efficient parallel strategies for two fundamental combinatorial search problems, namely, backtrack search and branch-and-bound, both involving the visit of an $n$-node tree of height $h$ under the assumption that a node can be accessed only through its father or its children. For both problems we propose efficient algorithms that run on a $p$-processor distributed-memory machine. For backtrack search, we give a deterministic algorithm running in $O(n/p+hlogp)$ time, and a Las Vegas algorithm requiring optimal $O(n/p+h)$ time, with high probability. Building on the backtrack search algorithm, we also derive a Las Vegas algorithm for branch-and-bound which runs in $O((n/p+hlogplogn)hlo{g}^{2}n)$ time, with high probability. A remarkable feature of our algorithms is the use of only constant space per processor, which constitutes a significant improvement upon previous algorithms whose space requirements per processor depend on the (possibly huge) tree to be explored.

Recommendations

• scientific article; zbMATH DE number 1163099
• Efficient massively parallel implementation of some combinatorial algorithms
• scientific article; zbMATH DE number 4037239
• scientific article; zbMATH DE number 4131653
• EFFICIENT PARALLEL RANGE SEARCHING AND PARTITIONING ALGORITHMS*
• scientific article; zbMATH DE number 686901
• Parallel Search Algorithms for Discrete Optimization Problems
• Parallel processing for difficult combinatorial optimization problems
• Parallel search algorithms for graphs and trees
• Design and research of the parallel combinatorial algorithms

Cited in

(16)

• Efficiency of randomized parallel backtrack search
• The parallel search bench ZRAM and its applications
• A criterion of optimality of some parallelization scheme for backtrack search problem in binary trees
• An analysis of budgeted parallel search on conditional Galton-Watson trees
• Randomized parallel algorithms for backtrack search and branch-and-bound computation
• Batched dynamic solutions to decomposable searching problems
• Optimal speedup for backtrack search on a butterfly network
• Branch-and-bound and backtrack search on mesh-connected arrays of processors
• scientific article; zbMATH DE number 1163099 (Why is no real title available?)
• scientific article; zbMATH DE number 1760141 (Why is no real title available?)
• scientific article; zbMATH DE number 2100400 (Why is no real title available?)
• scientific article; zbMATH DE number 2102781 (Why is no real title available?)
• scientific article; zbMATH DE number 934534 (Why is no real title available?)
• Deterministic branch-and-bound on distributed memory machines
• Parallel depth-bounded discrepancy search
• A nearly optimal randomized algorithm for explorable heap selection

This page was built for publication: Space-Efficient Parallel Algorithms for Combinatorial Search Problems

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