Randomized parallel algorithms for backtrack search and branch-and-bound computation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Randomized parallel algorithms for backtrack search and branch-and-bound computation

Full text

Pdf (1.85 MB)

Source

Journal of the ACM (JACM) archive
Volume 40 , Issue 3 (July 1993) table of contents

Pages: 765 - 789

Year of Publication: 1993

ISSN:0004-5411

Authors

Richard M. Karp	University of California at Berkeley, Berkeley, California
Yanjun Zhang	University of California at Berkeley, Berkeley, California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 44, Citation Count: 27

Additional Information:

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/174130.174145 What is a DOI?

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.

	6	Richard Karp , Yanjun Zhang, A randomized parallel branch-and-bound procedure, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.290-300, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62240]
	7	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
	8	Abhiram Ranade, A Simpler Analysis of the Karp-Zhang Parallel Branch-and-Bound Method, University of California at Berkeley, Berkeley, CA, 1990
	9	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 [doi>10.1145/113379.113383]
	10	~SP~NCER, J. Ten Lectures olz the Probabilistic Method. SIAM, Philadelphia, Pa., 1987.

CITED BY 27

	Robert D. Blumofe , Charles E. Leiserson, Scheduling multithreaded computations by work stealing, Journal of the ACM (JACM), v.46 n.5, p.720-748, Sept. 1999
	Jonathan Eckstein, Control strategies for parallel mixed integer branch and bound, Proceedings of the 1994 conference on Supercomputing, p.41-48, December 1994, Washington, D.C., United States
	Keqin Li, On dynamic tree growing in hypercubes, Proceedings of the 1997 ACM symposium on Applied computing, p.496-503, April 1997, San Jose, California, United States
	Susan Flynn Hummel , Jeanette Schmidt , R. N. Uma , Joel Wein, Load-sharing in heterogeneous systems via weighted factoring, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.318-328, June 24-26, 1996, Padua, Italy
	Robert D. Blumofe , Christopher F. Joerg , Bradley C. Kuszmaul , Charles E. Leiserson , Keith H. Randall , Yuli Zhou, Cilk: an efficient multithreaded runtime system, ACM SIGPLAN Notices, v.30 n.8, p.207-216, Aug. 1995
	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
	Keqin Li, Performance evaluation of probabilistic tree embedding in cube-connected cycles, Proceedings of the 1998 ACM symposium on Applied Computing, p.584-592, February 27-March 01, 1998, Atlanta, Georgia, United States
	Keqin Li, Maintenance of tree structured computations on parallel and distributed computer systems, Proceedings of the 1996 ACM symposium on Applied Computing, p.337-343, February 17-19, 1996, Philadelphia, Pennsylvania, United States
	Jonathan Eckstein, Control strategies for parallel mixed integer branch and bound, Proceedings of the 1994 ACM/IEEE conference on Supercomputing, November 14-18, 1994, Washington, D.C.
	Wei Shu , Min-You Wu, Runtime Incremental Parallel Scheduling (RIPS) on Distributed Memory Computers, IEEE Transactions on Parallel and Distributed Systems, v.7 n.6, p.637-649, June 1996
	Wolfgang Blochinger , Carsten Sinz , Wolfgang Küchlin, Parallel propositional satisfiability checking with distributed dynamic learning, Parallel Computing, v.29 n.7, p.969-994, July 2003
	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
	Keqin Li, On the performance of randomized embedding of reproduction trees in static networks, International Journal of Parallel Programming, v.31 n.5, p.393-406, October 2003
	Jonathan Eckstein, Distributed versus Centralized Storage and Control forParallel Branch and Bound: Mixed Integer Programming on the CM-5, Computational Optimization and Applications, v.7 n.2, p.199-220, March 1997
	Keqin Li, Analysis of randomized load distribution for reproduction trees in linear arrays and rings, Theoretical Computer Science, v.321 n.2-3, p.195-214, 16 August 2004
	Lixin Gao , Arnold L. Rosenberg , Ramesh K. Sitaraman, Optimal Clustering of Tree-Sweep Computations for High-Latency Parallel Environments, IEEE Transactions on Parallel and Distributed Systems, v.10 n.8, p.813-824, August 1999
	Kieran T. Herley , Andrea Pietracaprina , Geppino Pucci, Deterministic parallel backtrack search, Theoretical Computer Science, v.270 n.1-2, p.309-324, January
	Ananth Grama , Vipin Kumar, State of the Art in Parallel Search Techniques for Discrete Optimization Problems, IEEE Transactions on Knowledge and Data Engineering, v.11 n.1, p.28-35, January 1999
	Keqin Li, Design and analysis of asymptotically optimal randomized tree embedding algorithms in static networks, Performance Evaluation, v.60 n.1-4, p.141-163, May 2005
	Michal Kouril , Jerome L. Paul, A parallel backtracking framework (BkFr) for single and multiple clusters, Proceedings of the 1st conference on Computing frontiers, April 14-16, 2004, Ischia, Italy
	Nader Mohamed , Jameela Al-Jaroodi , Hong Jiang , David Swanson, JOPI: a Java object-passing interface, Proceedings of the 2002 joint ACM-ISCOPE conference on Java Grande, p.37-45, November 03-05, 2002, Seattle, Washington, USA
	Min-You Wu, On Runtime Parallel Scheduling for Processor Load Balancing, IEEE Transactions on Parallel and Distributed Systems, v.8 n.2, p.173-186, February 1997
	Nihar R. Mahapatra , Shantanu Dutt, Scalable Global and Local Hashing Strategies for Duplicate Pruning in Parallel A* Graph Search, IEEE Transactions on Parallel and Distributed Systems, v.8 n.7, p.738-756, July 1997
	Daniel J. Challou , Maria Gini , Vipin Kumar , George Karypis, Predicting the Performance of Randomized Parallel Search: An Application to Robot Motion Planning, Journal of Intelligent and Robotic Systems, v.38 n.1, p.31-53, September 2003
	Ricardo C. Corrêa , Valmir C. Barbosa, Partially ordered distributed computations on asynchronous point-to-point networks, Parallel Computing, v.35 n.1, p.12-28, January, 2009
	Sasa Misailovic , Aleksandar Milicevic , Nemanja Petrovic , Sarfraz Khurshid , Darko Marinov, Parallel test generation and execution with Korat, Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, September 03-07, 2007, Dubrovnik, Croatia
	Zineb Habbas , Michael Krajecki , Daniel Singer, Decomposition techniques for parallel resolution of constraint satisfaction problems in shared memory: a comparative study, International Journal of Computational Science and Engineering, v.1 n.2-4, p.192-206, May 2005