Towards an analysis of local optimization algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Towards an analysis of local optimization algorithms

Full text

Pdf (989 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-eighth annual ACM symposium on Theory of computing table of contents

Philadelphia, Pennsylvania, United States

Pages: 304 - 313

Year of Publication: 1996

ISBN:0-89791-785-5

Authors

Tassos Dimitriou	Department of Computer Science, University of California, San Diego, CA
Russell Impagliazzo	Department of Computer Science, University of California, San Diego, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 19, Citation Count: 3

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/237814.237882 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.

	Ald87	D. Aldous. On the markov chain simulation method for uniform combinatorial distributions and simulated annealing. Probability in the Engineering and Informational Sciences, 1:33-46, 1987.
	Alo86	N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
	AV94	D. Aldous and U. Vazirani. "Go with the winners" algorithms. In IEEE Symposium on Foundations of Computer Science (FOC$), pages 492-501, 1994.
	Bro86	A Z Broder, How hard is it to marry at random? (On the approximation of the permanent), Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.50-58, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12136]
	CR80	S. A. Cook and C. W. Rackoff. Space lower bounds for maze threadability on restricted machines. SIAM journal on Computing, 9(4):635- 652, 1980.
	DI95	T. Dimitriou and R. Impagliazzo. On the expansion of a random graph. Manuscript, 1995.
	JS88	Mark Jerrum , Alistair Sinclair, Conductance and the rapid mixing property for Markov chains: the approximation of permanent resolved, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.235-244, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62234]
	JS93	M.R. Jerrum and G. Sorkin.. Simulating annealing for graph bisection. In Proc. 3~h ~EEE Symposium on Foundations of Computer Science (FOC$), pages 94-103, 1993.
	SH88	Galen H. Sasaki , Bruce Hajek, The time complexity of maximum matching by simulated annealing, Journal of the ACM (JACM), v.35 n.2, p.387-403, April 1988 [doi>10.1145/42282.46160]

CITED BY 3

	Tassos Dimitriou , Russell Impagliazzo, Go with the winners for graph bisection, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.510-520, January 25-27, 1998, San Francisco, California, United States
	Christopher D. Rosin, Sample complexity of model-based search, Proceedings of the eleventh annual conference on Computational learning theory, p.259-267, July 24-26, 1998, Madison, Wisconsin, United States
	Ted Carson , Russell Impagliazzo, Hill-climbing finds random planted bisections, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.903-909, January 07-09, 2001, Washington, D.C., United States