{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T23:21:33Z","timestamp":1791328893366,"version":"4.3.1"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1989,12]]},"abstract":"<jats:p>A randomised approximation scheme for the permanent of a 0\u20131s presented. The task of estimating a permanent is reduced to that of almost uniformly generating perfect matchings in a graph; the latter is accomplished by simulating a Markov chain whose states are the matchings in the graph. For a wide class of 0\u20131 matrices the approximation scheme is fully-polynomial, i.e., runs in time polynomial in the size of the matrix and a parameter that controls the accuracy of the output. This class includes all dense matrices (those that contain sufficiently many 1\u2019s) and almost all sparse matrices in some reasonable probabilistic model for 0\u20131 matrices of given density.<\/jats:p>\n                  <jats:p>For the approach sketched above to be computationally efficient, the Markov chain must be rapidly mixing: informally, it must converge in a short time to its stationary distribution. A major portion of the paper is devoted to demonstrating that the matchings chain is rapidly mixing, apparently the first such result for a Markov chain with genuinely complex structure. The techniques used seem to have general applicability, and are applied again in the paper to validate a fully-polynomial randomised approximation scheme for the partition function of an arbitrary monomer-dimer system.<\/jats:p>","DOI":"10.1137\/0218077","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:32:44Z","timestamp":1109226764000},"page":"1149-1178","source":"Crossref","is-referenced-by-count":436,"title":["Approximating the Permanent"],"prefix":"10.1137","volume":"18","author":[{"given":"Mark","family":"Jerrum","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alistair","family":"Sinclair","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0068322"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1017\/S0269964800000267"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1986.11971821"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90092-9"},{"key":"R6","first-page":"1","volume-title":"Phase transitions and critical phenomena, Vol. 5b","author":"Binder K.","year":"1976"},{"key":"R7","volume-title":"Random graphs","author":"Bollob\u00e1s B\u00e9la","year":"1985"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"A. Z. Broder,  How hard is it to marry at random? (On the approximation of the permanent),  Proc. 18th Annual ACM Symposium on Theory of Computing,  1986,  50\u201358, Erratum in Proc. 20th Annual ACM Symposium on Theory of Computing, 1988, p. 551, Association for Computing Machinery, New York","DOI":"10.1145\/12130.12136"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"P. Dagum, M. Luby, M. Mihail, U. V. Vazirani,  Polytopes, permanents and graphs with large factors,  Proc. 29th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computing Society, Washington, DC,  1988","DOI":"10.1109\/SFCS.1988.21957"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/BF00535487"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"R12","unstructured":"P. Erdos, J. Spencer, Probabilistic methods in combinatorics, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1974, 106\u201352:2895"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1287\/moor.13.2.311"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01877590"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/BF01010403"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/0222021"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"R. M. Karp, M. Luby,  Monte-Carlo algorithms for enumeration and reliability problems,  Proc. 24th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computing Society, Washington, DC,  1983,  56\u201364","DOI":"10.1109\/SFCS.1983.35"},{"key":"R19","first-page":"43","volume-title":"Graph Theory and Theoretical Physics","author":"Kasteleyn P. W.","year":"1967"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-6200-8"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"key":"R22","first-page":"557","volume":"309","author":"Lawler Gregory F.","year":"1988","journal-title":"Trans. Amer. Math. Soc."},{"key":"R23","volume-title":"Matching theory","author":"Lov\u00e1sz L.","year":"1986"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582166"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90115-4"},{"key":"R26","volume-title":"Permanents","author":"Minc Henryk","year":"1978"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1145\/42282.46160"},{"key":"R28","unstructured":"A. J. Sinclair, Ph.D. Thesis,  Randomised algorithms for counting and generating combinatorial structures, University of Edinburgh, Edinburgh, Scotland,  1988, June"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90067-9"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"L. Stockmeyer,  The complexity of approximate counting,  Proc. 15th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, New York,  1983,  118\u2013126","DOI":"10.1145\/800061.808740"},{"key":"R31","volume-title":"Computational Aspects of VLSI","author":"Ullman J. D.","year":"1984"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"R34","unstructured":"A. Frieze,  A note on computing random permanents, unpublished manuscript"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0218077","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:45:39Z","timestamp":1787337939000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0218077"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,12]]},"references-count":34,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1989,12]]}},"alternative-id":["10.1137\/0218077"],"URL":"https:\/\/doi.org\/10.1137\/0218077","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,12]]}}}