Approximating the permanent

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Approximating the permanent

Source

SIAM Journal on Computing archive
Volume 18 , Issue 6 (December 1989) table of contents

Pages: 1149 - 1178

Year of Publication: 1989

ISSN:0097-5397

Authors

M. Jerrum	Univ. of Edinburgh, Edinburgh, Scotland, UK
Alistair Sinclair	Univ. of Edinburgh, Edinburgh, Scotland, UK

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): n/a, Downloads (12 Months): n/a, Citation Count: 66

Additional Information:

cited by index terms review collaborative colleagues

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

DOI Bookmark:	10.1137/0218077

CITED BY 67

	David Bruce Wilson, Generating random spanning trees more quickly than the cover time, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.296-303, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Sanjeev Arora , David Karger , Marek Karpinski, Polynomial time approximation schemes for dense instances of NP-hard problems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.284-293, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Russ Bubley , Martin Dyer , Catherine Greenhill, Beating the 2&Dgr; bound for approximately counting colourings: a computer-assisted proof of rapid mixing, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.355-363, January 25-27, 1998, San Francisco, California, United States
	Reuven Y. Rubinstein, Cross-entropy and rare events for maximal cut and partition problems, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.12 n.1, p.27-53, January 2002
	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
	Nathan Linial , Alex Samorodnitsky , Avi Wigderson, A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.644-652, May 24-26, 1998, Dallas, Texas, United States
	Ben Morris , Yuval Peres, Evolving sets and mixing, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Leonid Gurvits , Alex Samorodnitsky, A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.48-57, May 21-23, 2000, Portland, Oregon, United States
	Persi Diaconis , Laurent Saloff-Coste, What do we know about the Metropolis algorithm?, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.112-129, May 29-June 01, 1995, Las Vegas, Nevada, United States
	David R. Karger, A randomized fully polynomial time approximation scheme for the all terminal network reliability problem, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.11-17, May 29-June 01, 1995, Las Vegas, Nevada, 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
	Christos H. Papadimitriou , Hisao Tamaki , Prabhakar Raghavan , Santosh Vempala, Latent semantic indexing: a probabilistic analysis, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.159-168, June 01-04, 1998, Seattle, Washington, 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
	Stephen Guattery , Tom Leighton , Gary L. Miller, The path resistance method for bounding &lgr;2 of a Laplacian, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.201-210, January 05-07, 1997, New Orleans, Louisiana, United States
	Dana Randall , Alistair Sinclair, Testable algorithms for self-avoiding walks, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.593-602, January 23-25, 1994, Arlington, Virginia, United States
	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
	Alexander Gamburd , Igor Pak, Expansion of product replacement graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.691-696, January 06-08, 2002, San Francisco, California
	Fan R. K. Chung , S.-T. Yau, A near optimal algorithm for edge separators (preliminary version), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.1-8, May 23-25, 1994, Montreal, Quebec, Canada
	Jason Schweinsberg, An O(n²) bound for the relaxation time of a Markov chain on cladograms, Random Structures & Algorithms, v.20 n.1, p.59-70, January 2002
	Robert Els , Burkhard Monien, Load balancing of unit size tokens and expansion properties of graphs, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	David Bruce Wilson, Determinant algorithms for random planar structures, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.258-267, January 05-07, 1997, New Orleans, Louisiana, United States
	Sanjeev Arora , Yuval Rabani , Umesh Vazirani, Simulating quadratic dynamical systems is PSPACE-complete (preliminary version), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.459-467, May 23-25, 1994, Montreal, Quebec, Canada
	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
	Claire Kenyon , Dana Randall , Alistair Sinclair, Matchings in lattice graphs, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.738-746, May 16-18, 1993, San Diego, California, United States
	Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, ACM Computing Surveys (CSUR), v.28 n.1, p.33-37, March 1996
	David Bruce Wilson , James Gary Propp, How to get an exact sample from a generic Markov chain and sample a random spanning tree from a directed graph, both within the cover time, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.448-457, January 28-30, 1996, Atlanta, Georgia, United States
	Marcus Peinado , Thomas Lengauer, Random generation of embedded graphs and an extension to Dobrushin uniqueness (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.176-185, May 24-26, 1998, Dallas, Texas, United States
	Stephen Chenney , D. A. Forsyth, Sampling plausible solutions to multi-body constraint problems, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.219-228, July 2000
	Andris Ambainis , Eric Bach , Ashwin Nayak , Ashvin Vishwanath , John Watrous, One-dimensional quantum walks, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.37-49, July 2001, Hersonissos, Greece
	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
	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
	Marcus Peinado , Thomas Lengauer, Parallel 'go with the winners' algorithms in distributed memory models, Journal of Parallel and Distributed Computing, v.63 n.9, p.801-814, September 2003
	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
	Jianguo Qian , Fuji Zhang, Expanding and forwarding parameters of product graphs, Discrete Applied Mathematics, v.136 n.1, p.63-82, 30 January 2004
	Steve Chien, A determinant-based algorithm for counting perfect matchings in a general graph, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	N. Alon , F. R. K. Chung , R. L. Graham, Routing permutations on graphs via matchings, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.583-591, May 16-18, 1993, San Diego, California, United States
	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
	Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.222-231, June 13-16, 2004, Chicago, IL, USA
	Michael Korn , Igor Pak, Tilings of rectangles with T-tetrominoes, Theoretical Computer Science, v.319 n.1-3, p.3-27, June 10, 2004
	Isabel Beichl , Francis Sullivan, A = B?, Computing in Science and Engineering, v.2 n.3, p.84-87, May 2000
	Antar Bandyopadhyay , David Gamarnik, Counting without sampling: new algorithms for enumeration problems using statistical physics, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.890-899, January 22-26, 2006, Miami, Florida
	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
	Luca Trevisan , Salil Vadhan , David Zuckerman, Compression of samplable sources, Computational Complexity, v.14 n.3, p.186-227, January 2005
	Atish Das Sarma , Sreenivas Gollapudi , Rina Panigrahy, Estimating PageRank on graph streams, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada
	Nabil Kahale, Large Deviation Bounds for Markov Chains, Combinatorics, Probability and Computing, v.6 n.4, p.465-474, December 1997
	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
	Stephen Baumert , Archis Ghate , Seksan Kiatsupaibul , Yanfang Shen , Robert L. Smith , Zelda B. Zabinsky, Discrete Hit-and-Run for Sampling Points from Arbitrary Distributions Over Subsets of Integer Hyperrectangles, Operations Research, v.57 n.3, p.727-739, May 2009
	Nir Halman , Diego Klabjan , Chung-Lun Li , James Orlin , David Simchi-Levi, Fully polynomial time approximation schemes for stochastic dynamic programs, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.700-709, January 20-22, 2008, San Francisco, California
	László Lovász , Santosh Vempala, The geometry of logconcave functions and sampling algorithms, Random Structures & Algorithms, v.30 n.3, p.307-358, May 2007
	Lenore Cowen , Joan Feigenbaum , Sampath Kannan, A formal framework for evaluating heuristic programs, Annals of Mathematics and Artificial Intelligence, v.22 n.3-4, p.193-206, 1998
	Marc C. Robini , Yoram Bresler , Isabelle E. Magnin, ON THE CONVERGENCE OF METROPOLIS-TYPE RELAXATION AND ANNEALING WITH CONSTRAINTS, Probability in the Engineering and Informational Sciences, v.16 n.4, p.427-452, October 2002
	S. Guattery , T. Leighton , G. L. Miller, The Path Resistance Method for Bounding the Smallest Nontrivial Eigenvalue of a Laplacian, Combinatorics, Probability and Computing, v.8 n.5, p.441-460, September 1999
	S. Guattery , T. Leighton , G. L. Miller, The Path Resistance Method for Bounding the Smallest Nontrivial Eigenvalue of a Laplacian, Combinatorics, Probability and Computing, v.8 n.5, p.441-460, September 1999
	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
	Peter Mathé , Erich Novak, Simple Monte Carlo and the Metropolis algorithm, Journal of Complexity, v.23 n.4-6, p.673-696, August, 2007
	Daniel Rudolf, Explicit error bounds for lazy reversible Markov chain Monte Carlo, Journal of Complexity, v.25 n.1, p.11-24, February, 2009
	Mark Huber, Perfect simulation with exponential tails on the running time, Random Structures & Algorithms, v.33 n.1, p.29-43, August 2008
	Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Journal of the ACM (JACM), v.56 n.2, p.1-37, April 2009
	Páidí Creed, Sampling Eulerian orientations of triangular lattice graphs, Journal of Discrete Algorithms, v.7 n.2, p.168-180, June, 2009
	Antar Bandyopadhyay , David Gamarnik, Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models, Random Structures & Algorithms, v.33 n.4, p.452-479, December 2008
	Daniel Štefankovič , Santosh Vempala , Eric Vigoda, Adaptive simulated annealing: A near-optimal connection between sampling and counting, Journal of the ACM (JACM), v.56 n.3, p.1-36, May 2009
	Colin Cooper , Martin Dyer , Andrew J. Handley, The flip markov chain and a randomising P2P protocol, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada
	Nir Halman , Diego Klabjan , Mohamed Mostagir , Jim Orlin , David Simchi-Levi, A Fully Polynomial-Time Approximation Scheme for Single-Item Stochastic Inventory Control with Discrete Demand, Mathematics of Operations Research, v.34 n.3, p.674-685, August 2009
	Michael M. Zavlanos , Daniel E. Koditschek , George J. Pappas, A distributed dynamical scheme for fastest mixing Markov chains, Proceedings of the 2009 conference on American Control Conference, p.1436-1441, June 10-12, 2009, St. Louis, Missouri, USA
	Ishanu Chattopadhyay , Asok Ray, Supervised self-organization of homogeneous swarms using ergodic projections of Markov chains, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, v.39 n.6, p.1505-1515, December 2009

INDEX TERMS

Primary Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.1 Numerical Algorithms and Problems
Subjects: Computations on matrices

General Terms:
Algorithms, Theory

REVIEW

"David J. Aldous : Reviewer"

In previous work [1], the authors described an interesting and important technique for “approximate counting” of large combinatorial sets. The ingredients are (1) construction of a reversible Markov chain on the set with uniform st more...

Collaborative Colleagues:

M. Jerrum: colleagues

Alistair Sinclair: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player