Article

A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries

Authors:

Mark Jerrum,

Alistair Sinclair,

Eric VigodaAuthors Info & Claims

STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing

Pages 712 - 721

https://doi.org/10.1145/380752.380877

Published: 06 July 2001 Publication History

Get Access

Abstract

We present a fully-polynomial randomized approximation scheme for computing the permanent of an arbitrary matrix with non-negative entries.

References

[1]

Noga Alon and Joel Spencer,The Probabilistic Method John Wiley,1992.

Google Scholar

[2]

Alexander Barvinok,Polynomial time algorithms to approximate permanents and mixed discriminants within a simply exponential factor,Random Structures and Algorithms 14 (1999),29 -61.

Digital Library

Google Scholar

[3]

Andrei Z.Broder,How hard is it to marry at random? (On the approximation of the permanent),Proceedings of the 18th Annual ACM Symposium on Theory of Computing (STOC),ACM Press,1986,50 -58. Erratum in Proceedings of the 20th Annual ACM Symposium on Theory of Computing 1988,p.551.

Digital Library

Google Scholar

[4]

Mark Jerrum and Alistair Sinclair,Approximating the permanent,SIAM Journal on Computing 18 (1989), 1149 -1178.

Digital Library

Google Scholar

[5]

Mark Jerrum and Alistair Sinclair,Fast uniform generation of regular graphs,Theoretical Computer Science 73 (1990),91 -100.

Digital Library

Google Scholar

[6]

Mark Jerrum and Alistair Sinclair,The Markov chain Monte Carlo method:an approach to approximate counting and integration.In Approximation Algorithms for NP-hard Problems (Dorit Hochbaum, ed.),PWS,1996,482 -520.

Digital Library

Google Scholar

[7]

Mark Jerrum,Leslie Valiant and Vijay Vazirani, Random generation of combinatorial structures from a uniform distribution,Theoretical Computer Science 43 (1986),169 -188.

Digital Library

Google Scholar

[8]

Mark Jerrum and Umesh Vazirani,A mildly exponential approximation algorithm for the permanent,Algorithmica 16 (1996),392 -401.

Crossref

Google Scholar

[9]

P.W.Kasteleyn,The statistics of dimers on a lattice, I.,The number of dimer arrangements on a quadratic lattice,Physica 27 (1961)1664 -1672.

Crossref

Google Scholar

[10]

Nathan Linial,Alex Samorodnitsky and Avi Wigderson,A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents,Combinatorica 20 (2000),545 -568.

Crossref

Google Scholar

[11]

Milena Mihail and Peter Winkler,On the number of Eulerian orientations of a graph,Algorithmica 16 (1996),402 -414.

Crossref

Google Scholar

[12]

Henryk Minc,Permanents,Encyclopedia of Mathematics and its Applications 6 (1982), Addison-Wesley Publishing Company.

Google Scholar

[13]

Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms Cambridge University Press, 1995.

Digital Library

Google Scholar

[14]

W.T.Tutte,A short proof of the factor theorem for .nite graphs,Canadian Journal of Mathematics 6 (1954)347 -352.

Crossref

Google Scholar

[15]

L.G.Valiant,The complexity of computing the permanent, Theoretical Computer Science 8 (1979), 189 -201.

Crossref

Google Scholar

Cited By

View all

Babukhin DPogosov W(2022)The effect of quantum noise on algorithmic perfect quantum state transfer on NISQ processorsQuantum Information Processing10.1007/s11128-021-03346-z21:1Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1007/s11128-021-03346-z
Moulos V(2020)A Hoeffding Inequality for Finite State Markov Chains and its Applications to Markovian Bandits2020 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT44484.2020.9173931(2777-2782)Online publication date: Jun-2020
https://doi.org/10.1109/ISIT44484.2020.9173931
Acharyya RChakraborty SJha N(2014)Counting Popular Matchings in House Allocation ProblemsComputer Science - Theory and Applications10.1007/978-3-319-06686-8_4(39-51)Online publication date: 2014
https://doi.org/10.1007/978-3-319-06686-8_4
Show More Cited By

Index Terms

A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
1. Mathematics of computing
  1. Mathematical analysis
    1. Nonlinear equations
    2. Numerical analysis
      1. Computations on matrices
      2. Computations on polynomials

Recommendations

A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries

We present a polynomial-time randomized algorithm for estimating the permanent of an arbitrary n × n matrix with nonnegative entries. This algorithm---technically a "fully-polynomial randomized approximation scheme"---computes an approximation that is, ...
Shift-Invert Arnoldi Approximation to the Toeplitz Matrix Exponential

The shift-invert Arnoldi method is employed to generate an orthonormal basis from the Krylov subspace corresponding to a real Toeplitz matrix and an initial vector. The vectors and recurrence coefficients produced by this method are exploited to ...
Bounds for entries of the inverse matrix of a tridiagonal matrix

Inequalities for the moduli of entries of the inverse matrix of a tridiagonal matrix are obtained. These results are applicable to a relatively large family of matrices which occur in many branches of numerical analysis, applied mathematics, and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing

July 2001

755 pages

ISBN:1581133499

DOI:10.1145/380752

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC01

Sponsor:

SIGACT

STOC01: 33rd ACM Symposium on Theory of Computing

Hersonissos, Greece

Acceptance Rates

STOC '01 Paper Acceptance Rate 83 of 230 submissions, 36%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

60
Total Citations
View Citations
74
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Babukhin DPogosov W(2022)The effect of quantum noise on algorithmic perfect quantum state transfer on NISQ processorsQuantum Information Processing10.1007/s11128-021-03346-z21:1Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1007/s11128-021-03346-z
Moulos V(2020)A Hoeffding Inequality for Finite State Markov Chains and its Applications to Markovian Bandits2020 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT44484.2020.9173931(2777-2782)Online publication date: Jun-2020
https://doi.org/10.1109/ISIT44484.2020.9173931
Acharyya RChakraborty SJha N(2014)Counting Popular Matchings in House Allocation ProblemsComputer Science - Theory and Applications10.1007/978-3-319-06686-8_4(39-51)Online publication date: 2014
https://doi.org/10.1007/978-3-319-06686-8_4
Jiang XHuang JGuibas L(2011)Fourier-information duality in the identity management problemProceedings of the 2011 European conference on Machine learning and knowledge discovery in databases - Volume Part II10.5555/2034117.2034125(97-113)Online publication date: 5-Sep-2011
https://dl.acm.org/doi/10.5555/2034117.2034125
Jiang XHuang JGuibas L(2011)Fourier-information duality in the identity management problemProceedings of the 2011th European Conference on Machine Learning and Knowledge Discovery in Databases - Volume Part II10.1007/978-3-642-23783-6_7(97-113)Online publication date: 5-Sep-2011
https://dl.acm.org/doi/10.1007/978-3-642-23783-6_7
Bouchard-Côté AJordan M(2010)Variational inference over combinatorial spacesProceedings of the 24th International Conference on Neural Information Processing Systems - Volume 110.5555/2997189.2997221(280-288)Online publication date: 6-Dec-2010
https://dl.acm.org/doi/10.5555/2997189.2997221
Zanarini APesant G(2009)Solution counting algorithms for constraint-centered search heuristicsConstraints10.1007/s10601-008-9065-914:3(392-413)Online publication date: 1-Sep-2009
https://dl.acm.org/doi/10.1007/s10601-008-9065-9
Aharonov DJones VLandau Z(2009)A Polynomial Quantum Algorithm for Approximating the Jones PolynomialAlgorithmica10.1007/s00453-008-9168-055:3(395-421)Online publication date: 16-Jun-2009
https://dl.acm.org/doi/10.1007/s00453-008-9168-0
Björklund AHusfeldt T(2008)Exact Algorithms for Exact Satisfiability and Number of Perfect MatchingsAlgorithmica10.5555/3118777.311918652:2(226-249)Online publication date: 1-Oct-2008
https://dl.acm.org/doi/10.5555/3118777.3119186
Lakshmanan LNg RRamesh G(2008)On disclosure risk analysis of anonymized itemsets in the presence of prior knowledgeACM Transactions on Knowledge Discovery from Data10.1145/1409620.14096232:3(1-44)Online publication date: 27-Oct-2008
https://dl.acm.org/doi/10.1145/1409620.1409623
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries

Shift-Invert Arnoldi Approximation to the Toeplitz Matrix Exponential

Bounds for entries of the inverse matrix of a tridiagonal matrix