Randomized parallel algorithms for backtrack search and branch-and-bound computation
Copyright policy )Randomized parallel algorithms for backtrack search and branch-and-bound computation
Backtracking and Branch-and-Bound are the main methods for solving combinatorial search and optimization problems. The paper proposes two randomized schemas for implementing the two methods in their full generality in a message-passing multiprocessor system with a constant number of processors. A careful probabilistic analysis shows that with high probability the proposed algorithms achieve within a constant factor the optimal theoretic speed-up. The paper is of great interest for both algorithms and distributed systems specialists.
- University of California, Berkeley United States
Backtrack search, Analysis of algorithms and problem complexity, Distributed algorithms, branch-and-bound, Combinatorics in computer science, distributed parallel computation
Backtrack search, Analysis of algorithms and problem complexity, Distributed algorithms, branch-and-bound, Combinatorics in computer science, distributed parallel computation
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).122 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 1% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!