How hard is it to marry at random? (On the approximation of the permanent)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

How hard is it to marry at random? (On the approximation of the permanent)

Full text

Pdf (645 KB)

Source

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

Berkeley, California, United States

Pages: 50 - 58

Year of Publication: 1986

ISBN:0-89791-193-8

Author

A Z Broder

DEC, Systems Research Center, 130 Lytton Avenue, Palo Alto, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 78, Citation Count: 25

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

	AD85	D. Aldous and P. Diaconis, aShuffling cai~ds and stopping times, ~ to appear, 1985.
	Aldous83	D. Aldous, ``Randomwall~s on finite groups and rapidly mixing Markov chains, = Seminaire de Probabilit~s XVll.Springer-Verlag, 1983, 243-297
	Broder84	A. Broder, ~'Shuffling cards" the slow way," manuscript, 1984.
	CVCS3	F. K. Chung, P. Diaconis, and R. L. Graham, "Random walks arising from random number generation," Technical report no. 212, Department of Statistics, Stanford University, 1983.
	D85	P. Diaconis, Group Theory in Statistics, in preparation.
	DS81	P. Diaconis and M. Shahshahani, "Generating a random permutation with random transpositions, ~ Z. Wahr. Verw. Gebiete, 57(1981), 159--179.
	FOW85	L. Flatto, A. M. Odlyzko, and D. B. Wales, "Random shuffles and group representation, ~ The Annals of Probability, 18(1985), 154-178.
	Griifeath78	D. Griffeath, "Coupling methods for Markov processes, ~ in: J. C. Rots (ed), Studies in Probability and Ergodic Theory, Advances in Mathematics, Supplementary Studies, VoL 2, Academic Press, 1978.
	Ja´ ja ´ 83	J. Ja" ja" , "On the computational complexity of the permanent, ~ FOCS, 1983.
	Jvvss	M. R. Jerrum, L. G. Valiant, and V. V. Vazirani, "Random generation of combinatorial structures from a uniform distribution, ~ Technical report CSR-187-85, University of Edinburgh, Department of Computer Science, 1985.
	KL83	R. Karl) and M. Luby, "Monte Carlo algorithms for enumeration and reliability problems,,, STOC, 1983.
	Knuth81	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	Luby84	M. Luby, "Class notes for CSC2408S, ~ Toronto, 1984.
	Minc78	H. Minc, Permanents, Addison-Wesley, 1978.
	NW75	A. Nijenhuis and H. Will, Combinatorial Aloorithms, New York, 1975.
	RyserB3	H. J. Ryser, Combinatorial Mathematics, MAA, 1963.
	Stockmeyer83	L. Stockmeyer, "On approximation algorithms for ~P,,, STOC, 1983.
	Sturtivant82	C. Sturtivant, "Generalized symmetries of polynomials and algebraic complexity," FOCS, 1982.
	wss	L G Valiant , V V Vazirani, NP is as easy as detecting unique solutions, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.458-463, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22196]
	Valiant79	L. Valiant, "The complexity of computing the permanent," TCS, 8(1979), 189--201.
	w 77	H. S. Will, UA unified setting for sequencing, ranking, and selection algorithms for combinatorial objects,,, Advances in Mathematics, 24(1977), 281-291.

CITED BY 25

	Prasad Tetali , Peter Winkler, On a random walk problem arising in self-stabilizing token management, Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.273-280, August 19-21, 1991, Montreal, Quebec, Canada
	Tassos Dimitriou , Russell Impagliazzo, Towards an analysis of local optimization algorithms, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.304-313, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	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
	Milena Mihail , Peter Winkler, On the number of Eularian orientations of a graph, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.138-145, September 1992, Orlando, Florida, United States
	Martin Dyer , Alan Frieze , Ravi Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies, Journal of the ACM (JACM), v.38 n.1, p.1-17, Jan. 1991
	Tomás Feder , Milena Mihail, Balanced matroids, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.26-38, May 04-06, 1992, Victoria, British Columbia, Canada
	Ketan Mulmuley , Umesh V. Vazirani , Vijay V. Vazirani, Matching is as easy as matrix inversion, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.345-354, January 1987, New York, New York, United States
	Uriel Feige , Carsten Lund, On the hardness of computing the permanent of random matrices (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.643-654, May 04-06, 1992, Victoria, British Columbia, Canada
	Martin Dyer , Alan Frieze , Mark Jerrum, Approximately counting Hamilton cycles in dense graphs, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.336-343, January 23-25, 1994, Arlington, Virginia, United States
	Wu-Lin Chen , Colm Art O'Cinneide, Towards a polynomial-time randomized algorithm for closed product-form networks, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.3, p.227-253, July 1998
	Mark Jerrum , Alistair Sinclair , Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.712-721, July 2001, Hersonissos, Greece
	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	Greg Barnes , Uriel Feige, Short random walks on graphs, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.728-737, May 16-18, 1993, San Diego, California, United States
	Rajeev Motwani, Average-case analysis of algorithms for matchings and related problems, Journal of the ACM (JACM), v.41 n.6, p.1329-1356, Nov. 1994
	Martin Fürer, Approximating permanents of complex matrices, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.667-669, May 21-23, 2000, Portland, Oregon, United States
	P. Dagum , R. M. Chavez, Approximating Probabilistic Inference in Bayesian Belief Networks, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.3, p.246-255, March 1993
	Steve Chien , Lars Rasmussen , Alistair Sinclair, Clifford algebras and approximating the permanent, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Mark Jerrum , Alistair Sinclair , Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, Journal of the ACM (JACM), v.51 n.4, p.671-697, July 2004
	Steve Chien , Lars Rasmussen , Alistair Sinclair, Clifford algebras and approximating the permanent, Journal of Computer and System Sciences, v.67 n.2, p.263-290, September 2003
	R. Motwani, Expanding graphs and the average-case analysis of algorithms for matchings and related problems, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.550-561, May 14-17, 1989, Seattle, Washington, United States
	M. Dyer , A. Frieze, A random polynomial time algorithm for approximating the volume of convex bodies, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.375-381, May 14-17, 1989, Seattle, Washington, United States
	Ivona Bezáková , Daniel Štefankovič , Vijay V. Vazirani , Eric Vigoda, Accelerating simulated annealing for the permanent and combinatorial counting problems, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.900-907, January 22-26, 2006, Miami, Florida
	Joan Feigenbaum , Yuval Ishai , Tal Malkin , Kobbi Nissim , Martin J. Strauss , Rebecca N. Wright, Secure multiparty computation of approximations, ACM Transactions on Algorithms (TALG), v.2 n.3, p.435-472, July 2006
	Lane A. Hemaspaandra, SIGACT news complexity theory column 51, ACM SIGACT News, v.37 n.2, June 2006
	Mark Huber , Jenny Law, Fast approximation of the permanent for very dense problems, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.681-689, January 20-22, 2008, San Francisco, California