Abstract
Randomized algorithms are algorithms that employ randomness in their solution method. We show that the performance of randomized algorithms is less affected by factors that prevent most parallel deterministic algorithms from attaining their theoretical speedup bounds. A major reason is that the mapping of randomized algorithms onto multiprocessors involves very little scheduling or communication overhead. Furthermore, reliability is enhanced because the failure of a single processor leads only to degradation, not failure, of the algorithm. We present results of an extensive simulation done on a multiprocessor simulator, running a randomized branch-and-bound algorithm. The particular case we consider is the knapsack problem, due to its ease of formulation. We observe the largest speedups in precisely those problems that take large amounts of time to solve.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
A. C. Yao, Probabilistic Computations: Toward a Unified Measure of Complexity, inProc. 18th Annual IEEE Symp. on Fundamentals of Computer Science, New York, pp. 222–237 (1977).
W. Dobosiewicz, Sorting by Distributive Partitioning,Inf. Proc. Lett., Vol. 7, No. 1, (January 1978).
M. O. Ruban, Probabilistic Algorithm in Finite Fields, Technical Report, Massachusetts Institute of Technology (1979).
P. G. Spirakis, Probabilistic Algorithms, Algorithms with Random Inputs and Random Combinatorial Structures, Ph.D. thesis, Harvard University, Department of Mathematics (December 1981).
G. L. Thompson and S. Singhal, A Successful Algorithm for Solving Directed Hamiltonian Path Problems,Operations Research Letters,3(12):35–42 (April 1984).
M. O. Rabin, Probabilistic Algorithms, inAlgorithms and Complexity, J.F. Traub (ed.), Academic Press, pp. 21–39 (1976).
D. Vrsalovic, D. P. Siewiorek, Z. Z. Segall, and E. F. Gehringer, Performance Prediction for Multiprocessor Systems, inProc. 13th Intl. Conf. on Parallel Processing, pp. 139–146 (August 1984).
G. M. Baudet, The Design and Analysis of Algorithms for Asynchronous Multiprocessors, Ph.D. thesis, Technical Report CMU-CS-78-116, Carnegie-Mellon University Department of Computer Science (April 1978).
E. F. Gehringer, A. K. Jones, and Z. Z. Segall, The Cm* Testbed,IEEE Computer, pp. 40–53 (October 1982).
V. K. Janakiram, D. P. Agrawal, and R. Mehrotra, Randomized Parallel Algorithms for PROLOG Programs and Backtracking Applications, inProc. 1987 Intl. Conf. on Parallel Processing, Chicago, Illinois, pp. 278–282 (1987).
H. S. Stone and P. Sipala, The Average Complexity of Depth-First Search with Backtracking and Cutoff,IBM J. of Res and Development,30(3):242–258 (May 1986).
R. S. Garfinkel and A. L. Nemhauser,Integer Programming, New York, John Wiley & Sons, Inc. (1972).
B. Lagewes, J. Lenston, and A. Rennooy Kan, Job-shop Scheduling by Implicit Enumeration,Management Science,24(4) (1977).
G. Ingangiole and J. Korsh, A Reduction Algorithm for Zero-one Single Knapsack Problems,Management Science,20(4):460–663 (1973).
G. Ingangiole and J. Korsh, A General Algorithm for One-dimensional Knapsack Problems,Operations Research,25(5):752–759 (1977).
R. Garfinkel, On Partitioning the Feasible Set in a Branch-and-bound Algorithm for the Asymmetric Traveling Salesman Problem,Operations Research,21(9):340–342 (1973).
A. Efroymson and T. C. Ray, A Branch-and-bound Algorithm for Plant Location,Operations Research,14:361–368 (1966).
A. M. Geoffrion and R. E. Marston, Integer Programming Algorithms: A Framework and State-of-the-art Survey,Management Science,18(9):465–491 (May 1972).
T. Lai and S. Sahni, Anomalies in Parallel Branch-and-bound Algorithms, inProc. 1983 Intl. Conf. Parallel Processing, Bellaire, Michigan, pp. 183–190 (1983).
B. W. Wah and Y. W. Eva Ma, MANIP—A Multicomputer Architecture for Solving Combinatorial Extremum-search Problems,IEEE Trans. on Computers,C-33(5):377–390 (May 1984).
B. W. Wah and C. F. Yu, Probabilistic Modelling of Branch and Bound Algorithms, inProc. of the COMPSAC, pp. 647–653 (1982).
O. I. El-Dessouki and W. H. Huen, Distributed Enumeration on Network Computers,IEEE Transactions on Computers,C-29(9):818–825 (Sept. 1980).
D. R. Smith, Random Trees and the Analysis of Branch-and-bound Procedures.J. ACM,31(1):163–188 (January 1984).
B. W. Wah and C. F. Yu, Stochastic Modeling of Branch-and-bound Algorithms with Best-first Search,IEEE Trans. on Software Eng.,SE-11(9):922–933 (September 1985).
A. H. Stroud and D. Secrest,Gaussian Quadrature Formulas, New Jersey, Prentice-Hall (1966).
N. G. De Bruijn,Asymptotic Methods in Analysis, Amsterdam, North Holland Publishing Co. (1961).
W. Feller,An Introduction to Probability Theory and Applications, New York, Wiley (1971).
E. D. Brooks, A Multitasking Kernal for the C and Fortran Programming Languages, Tech. Rep. UCID 20167, Lawerence Livermore National Laboratory, Livermore, California (September 1984).
E. Horowitz and S. Sahni,Fundamentals of Computer Algorithms, Maryland, Computer Science Press (1984).
Author information
Authors and Affiliations
Additional information
This work has been supported by the U.S. Army Research Office under Contract No. DAAG 29-85-K-0236.
Rights and permissions
About this article
Cite this article
Janakiram, V.K., Gehringer, E.F., Agrawal, D.P. et al. A randomized parallel branch-and-bound algorithm. Int J Parallel Prog 17, 277–301 (1988). https://doi.org/10.1007/BF02427853
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02427853