{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,10]],"date-time":"2024-08-10T18:30:47Z","timestamp":1723314647197},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2004,7]]},"abstract":"\n We present a polynomial-time randomized algorithm for estimating the permanent of an arbitrary\n n<\/jats:italic>\n \u00d7\n n<\/jats:italic>\n matrix with nonnegative entries. This algorithm---technically a \"fully-polynomial randomized approximation scheme\"---computes an approximation that is, with high probability, within arbitrarily small specified relative error of the true value of the permanent.\n <\/jats:p>","DOI":"10.1145\/1008731.1008738","type":"journal-article","created":{"date-parts":[[2004,7,20]],"date-time":"2004-07-20T16:39:33Z","timestamp":1090341573000},"page":"671-697","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":343,"title":["A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries"],"prefix":"10.1145","volume":"51","author":[{"given":"Mark","family":"Jerrum","sequence":"first","affiliation":[{"name":"University of Edinburgh, Edinburgh, United Kingdom"}]},{"given":"Alistair","family":"Sinclair","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, Berkeley, California"}]},{"given":"Eric","family":"Vigoda","sequence":"additional","affiliation":[{"name":"University of Chicago, Chicago, Illinois"}]}],"member":"320","published-online":{"date-parts":[[2004,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1017\/S0269964800000267","article-title":"On the Markov chain simulation method for uniform combinatorial distributions and simulated annealing","volume":"1","author":"Aldous D.","year":"1987","unstructured":"Aldous , D. 1987 . On the Markov chain simulation method for uniform combinatorial distributions and simulated annealing . Prob. Eng. Inf. Sci. 1 , 33 -- 46 . Aldous, D. 1987. On the Markov chain simulation method for uniform combinatorial distributions and simulated annealing. Prob. Eng. Inf. Sci. 1, 33--46.","journal-title":"Prob. Eng. Inf. Sci."},{"key":"e_1_2_1_2_1","unstructured":"Alon N. and Spencer J. 1992. The Probabilistic Method. Wiley New York. Alon N. and Spencer J. 1992. The Probabilistic Method. Wiley New York."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(1999010)14:1%3C29::AID-RSA2%3E3.0.CO;2-X"},{"key":"e_1_2_1_4_1","first-page":"551","volume-title":"Proceedings of the 18th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 50--58. (Erratum in Proceedings of the 20th Annual ACM Symposium on Theory of Computing","author":"Broder A. Z.","year":"1986","unstructured":"Broder , A. Z. 1986 . How hard is it to marry at random? (On the approximation of the permanent) . In Proceedings of the 18th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 50--58. (Erratum in Proceedings of the 20th Annual ACM Symposium on Theory of Computing , 1988, p. 551 .) 10.1145\/12130.12136 Broder, A. Z. 1986. How hard is it to marry at random? (On the approximation of the permanent). In Proceedings of the 18th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 50--58. (Erratum in Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988, p. 551.) 10.1145\/12130.12136"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 34th Annual ACM Symposium on Theory of Computing, ACM","author":"Chien S.","unstructured":"Chien , S. , Rasmussen , L. , and Sinclair , A . 2002. Clifford algebras and approximating the permanent . In Proceedings of the 34th Annual ACM Symposium on Theory of Computing, ACM , New York, 222--231. 10.1145\/509907.509944 Chien, S., Rasmussen, L., and Sinclair, A. 2002. Clifford algebras and approximating the permanent. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing, ACM, New York, 222--231. 10.1145\/509907.509944"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"696","DOI":"10.1214\/aoap\/1177005359","article-title":"Comparison theorems for reversible Markov chains","volume":"3","author":"Diaconis P.","year":"1993","unstructured":"Diaconis , P. , and Saloff-Coste , L. 1993 . Comparison theorems for reversible Markov chains . Ann. Appl. Prob. 3 , 696 -- 730 . Diaconis, P., and Saloff-Coste, L. 1993. Comparison theorems for reversible Markov chains. Ann. Appl. Prob. 3, 696--730.","journal-title":"Ann. Appl. Prob."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1214\/aoap\/1177005980","article-title":"Geometric bounds for eigenvalues of Markov chains","volume":"1","author":"Diaconis P.","year":"1991","unstructured":"Diaconis , P. , and Stroock , D. 1991 . Geometric bounds for eigenvalues of Markov chains . Ann. Appl. Prob. 1 , 36 -- 61 . Diaconis, P., and Stroock, D. 1991. Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Prob. 1, 36--61.","journal-title":"Ann. Appl. Prob."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794268765"},{"key":"e_1_2_1_9_1","volume-title":"Lectures in Mathematics---ETH Z\u00fcrich","author":"Jerrum M.","unstructured":"Jerrum , M. 2003. Counting , sampling and integrating: Algorithms and complexity . In Lectures in Mathematics---ETH Z\u00fcrich . Birkh\u00e4user , Basel . Jerrum, M. 2003. Counting, sampling and integrating: Algorithms and complexity. In Lectures in Mathematics---ETH Z\u00fcrich. Birkh\u00e4user, Basel."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(90)90164-D"},{"key":"e_1_2_1_12_1","unstructured":"Jerrum M. and Sinclair A. 1996. The Markov chain Monte Carlo method: An approach to approximate counting and integration. In Approximation Algorithms for NP-hard Problems (Dorit Hochbaum ed.). PWS Publishing 482--520. Jerrum M. and Sinclair A. 1996. The Markov chain Monte Carlo method: An approach to approximate counting and integration. In Approximation Algorithms for NP-hard Problems (Dorit Hochbaum ed.). PWS Publishing 482--520."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","article-title":"Random generation of combinatorial structures from a uniform distribution","volume":"43","author":"Jerrum M.","year":"1986","unstructured":"Jerrum , M. , Valiant , L. , and Vazirani , V. 1986 . Random generation of combinatorial structures from a uniform distribution . Theoret. Comput. Sci. 43 , 169 -- 188 . Jerrum, M., Valiant, L., and Vazirani, V. 1986. Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci. 43, 169--188.","journal-title":"Theoret. Comput. Sci."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1007\/BF01940871","article-title":"A mildly exponential approximation algorithm for the permanent","volume":"16","author":"Jerrum M.","year":"1996","unstructured":"Jerrum , M. , and Vazirani , U. 1996 . A mildly exponential approximation algorithm for the permanent . Algorithmica 16 , 392 -- 401 . Jerrum, M., and Vazirani, U. 1996. A mildly exponential approximation algorithm for the permanent. Algorithmica 16, 392--401.","journal-title":"Algorithmica"},{"key":"e_1_2_1_15_1","first-page":"1664","article-title":"The statistics of dimers on a lattice, I., The number of dimer arrangements on a quadratic lattice","volume":"27","author":"Kasteleyn P. W.","year":"1961","unstructured":"Kasteleyn , P. W. 1961 . The statistics of dimers on a lattice, I., The number of dimer arrangements on a quadratic lattice . Physica 27 , 1664 -- 1672 . Kasteleyn, P. W. 1961. The statistics of dimers on a lattice, I., The number of dimer arrangements on a quadratic lattice. Physica 27, 1664--1672.","journal-title":"Physica"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1007\/BF02183743","article-title":"Approximating the number of dimer coverings of a lattice","volume":"83","author":"Kenyon C.","year":"1996","unstructured":"Kenyon , C. , Randall , D. , and Sinclair , A. 1996 . Approximating the number of dimer coverings of a lattice . J. Stat. Phys. 83 , 637 -- 659 . Kenyon, C., Randall, D., and Sinclair, A. 1996. Approximating the number of dimer coverings of a lattice. J. Stat. Phys. 83, 637--659.","journal-title":"J. Stat. Phys."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1214\/aoap\/1028903453","article-title":"Chernoff-type bounds for finite Markov chains","volume":"8","author":"Lezaud P.","year":"1998","unstructured":"Lezaud , P. 1998 . Chernoff-type bounds for finite Markov chains . Ann. Appl. Prob. 8 , 849 -- 867 . Lezaud, P. 1998. Chernoff-type bounds for finite Markov chains. Ann. Appl. Prob. 8, 849--867.","journal-title":"Ann. Appl. Prob."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1007\/s004930070007","article-title":"A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents","volume":"20","author":"Linial N.","year":"2000","unstructured":"Linial , N. , Samorodnitsky , A. , and Wigderson , A. 2000 . A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents . Combinatorica 20 , 545 -- 568 . Linial, N., Samorodnitsky, A., and Wigderson, A. 2000. A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents. Combinatorica 20, 545--568.","journal-title":"Combinatorica"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, ACM","author":"Mihail M.","unstructured":"Mihail , M. , and Winkler , P . 1992. On the number of Eulerian orientations of a graph . In Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, ACM , New York, 138--145. Mihail, M., and Winkler, P. 1992. On the number of Eulerian orientations of a graph. In Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 138--145."},{"key":"e_1_2_1_20_1","volume-title":"Encyclopedia of Mathematics and Its Applications","author":"Minc H.","unstructured":"Minc , H. 1982. Permanents . Encyclopedia of Mathematics and Its Applications Vol. 6 , Addison-Wesley , Reading, Mass . Minc, H. 1982. Permanents. Encyclopedia of Mathematics and Its Applications Vol. 6, Addison-Wesley, Reading, Mass."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press Cambridge Mass. Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press Cambridge Mass.","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_22_1","volume-title":"Combinatorial Mathematics. The Carus Mathematical Monographs No. 14","author":"Ryser H. J.","unstructured":"Ryser , H. J. 1963. Combinatorial Mathematics. The Carus Mathematical Monographs No. 14 , Mathematical Association of America . Ryser, H. J. 1963. Combinatorial Mathematics. The Carus Mathematical Monographs No. 14, Mathematical Association of America."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10000"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1017\/S0963548300000390","article-title":"Improved bounds for mixing rates of Markov chains and multicommodity flow","volume":"1","author":"Sinclair A.","year":"1992","unstructured":"Sinclair , A. 1992 . Improved bounds for mixing rates of Markov chains and multicommodity flow . Combinatorics, Probability and Computing 1 , 351 -- 370 . Sinclair, A. 1992. Improved bounds for mixing rates of Markov chains and multicommodity flow. Combinatorics, Probability and Computing 1, 351--370.","journal-title":"Combinatorics, Probability and Computing"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"347","DOI":"10.4153\/CJM-1954-033-3","article-title":"A short proof of the factor theorem for finite graphs","volume":"6","author":"Tutte W. T.","year":"1954","unstructured":"Tutte , W. T. 1954 . A short proof of the factor theorem for finite graphs . Canad. J. Math. 6 , 347 -- 352 . Tutte, W. T. 1954. A short proof of the factor theorem for finite graphs. Canad. J. Math. 6, 347--352.","journal-title":"Canad. J. Math."},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","article-title":"The complexity of computing the permanent","volume":"8","author":"Valiant L. G.","year":"1979","unstructured":"Valiant , L. G. 1979 . The complexity of computing the permanent . Theoret. Comput. Sci. 8 , 189 -- 201 . Valiant, L. G. 1979. The complexity of computing the permanent. Theoret. Comput. Sci. 8, 189--201.","journal-title":"Theoret. Comput. Sci."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1008731.1008738","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T15:43:48Z","timestamp":1672242228000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1008731.1008738"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,7]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2004,7]]}},"alternative-id":["10.1145\/1008731.1008738"],"URL":"https:\/\/doi.org\/10.1145\/1008731.1008738","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,7]]},"assertion":[{"value":"2004-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}