A randomized parallel branch-and-bound procedure

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A randomized parallel branch-and-bound procedure

Full text

Pdf (1.15 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twentieth annual ACM symposium on Theory of computing table of contents

Chicago, Illinois, United States

Pages: 290 - 300

Year of Publication: 1988

ISBN:0-89791-264-0

Authors

Richard Karp	Computer Science Division, Univesity of California, Berkeley, CA
Yanjun Zhang	Computer Science Division, Univesity of California, Berkeley, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 29, Citation Count: 18

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/62212.62240 What is a DOI?

ABSTRACT

We present a universal randomized method called Local Best-First Search for parallelizing sequential branch-and-bound algorithms. The method executes on a message-passing multiprocessor system, and requires no global data structures or complex communication protocols. We show that, uniformly on all instances, the execution time of the method is unlikely to exceed a certain inherent lower bound by more than a constant factor.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	D. Angluin, L.G. Valiant, Fast. probabilistic algorithms for llamiltonian circuits and matchings, J. Comput. $ystc,a Sci., 19 (1979'), 155-193.
	2	E. Balas, Branch and bound methods, in The Traveling Salesman Problem, edited by E.L. Lawler ~t al, John Wiley & Soils Ltd., 1985.
	3	J.L. Doob, Stochastic Process, John Wiley&; Sons. Inc. 1953.
	4	R.M. Karp, M. Saks and A. Wigderson, "On a Search Problem Related to Branch-and-Bound Procedures", Proc. ~7~h IEEE Symposium on Foundations of Computer Science, 19-28, 1986.
	5	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
	6	E. Shamir , J. Spencer, Sharp concentration of the chromatic number on random graphs Gn,p, Combinatorica, v.7 n.1, p.121-129, Jan. 1987 [doi>10.1007/BF02579208]
	7	Oliver Vornberger, Load Balancing in a Network of Transputers, Proceedings of the 2nd International Workshop on Distributed Algorithms, p.116-126, July 08-10, 1987
	8	B.W. Wah, G. Li, C.F. Yu, Multiprocessing of Combinatorial Search Problems, IEEE Computer, June 1985.

CITED BY 18

	Bhaskar Ghosh , S. Muthukrishnan, Dynamic load balancing in parallel and distributed networks by random matchings (extended abstract), Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.226-235, June 27-29, 1994, Cape May, New Jersey, United States
	Bhaskar Ghosh , F. T. Leighton , Bruce M. Maggs , S. Muthukrishnan , C. Greg Plaxton , R. Rajaraman , Andréa W. Richa , Robert E. Tarjan , David Zuckerman, Tight analyses of two local load balancing algorithms, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.548-558, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Girija J. Narlikar, Scheduling threads for low space requirement and good locality, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.83-95, June 27-30, 1999, Saint Malo, France
	Lars S. Nyland , Jan F. Prins , Allen Goldberg , Peter H. Mills, A Design Methodology for Data-Parallel Applications, IEEE Transactions on Software Engineering, v.26 n.4, p.293-314, April 2000
	Alexandros V. Gerbessiotis , Constantinos J. Siniolakis, Architecture independent parallel selection with applications to parallel priority queues, Theoretical Computer Science, v.301 n.1-3, p.119-142, 14 May 2003
	Abhiram Ranade, Optimal speedup for backtrack search on a butterfly network, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.40-48, July 21-24, 1991, Hilton Head, South Carolina, United States
	Pangfeng Liu , William Aiello , Sandeep Bhatt, An atomic model for message-passing, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.154-163, June 30-July 02, 1993, Velen, Germany
	Robert D. Blumofe , Charles E. Leiserson, Space-efficient scheduling of multithreaded computations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.362-371, May 16-18, 1993, San Diego, California, United States
	Richard M. Karp , Yanjun Zhang, Randomized parallel algorithms for backtrack search and branch-and-bound computation, Journal of the ACM (JACM), v.40 n.3, p.765-789, July 1993
	Michael Mitzenmacher, Analyses of load stealing models based on differential equations, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.212-221, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Christos Kaklamanis , Giuseppe Persiano, Branch-and-bound and backtrack search on mesh-connected arrays of processors, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.118-126, June 29-July 01, 1992, San Diego, California, United States
	Umut A. Acar , Guy E. Blelloch , Robert D. Blumofe, The data locality of work stealing, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.1-12, July 09-13, 2000, Bar Harbor, Maine, United States
	Sandeep Bhatt , Jin-Yi Cai, Taking random walks to grow trees in hypercubes, Journal of the ACM (JACM), v.40 n.3, p.741-764, July 1993
	M. K. Yang , C. R. Das, Evaluation of a Parallel Branch-and-Bound Algorithm on a Class of Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.5 n.1, p.74-86, January 1994
	Kunal Agrawal , Yuxiong He , Charles E. Leiserson, Adaptive work stealing with parallelism feedback, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA
	Giuseppe Di Fatta , Michael R. Berthold, Decentralized load balancing for highly irregular search problems, Microprocessors & Microsystems, v.31 n.4, p.273-281, June, 2007
	T. Leighton , M. Newman , A. G. Ranade , E. Schwabe, Dynamic tree embeddings in butterflies and hypercubes, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.224-234, June 18-21, 1989, Santa Fe, New Mexico, United States
	Kunal Agrawal , Charles E. Leiserson , Yuxiong He , Wen Jing Hsu, Adaptive work-stealing with parallelism feedback, ACM Transactions on Computer Systems (TOCS), v.26 n.3, p.1-32, September 2008