{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:22:31Z","timestamp":1759638151540},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540240587"},{"type":"electronic","value":"9783540305385"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30538-5_22","type":"book-chapter","created":{"date-parts":[[2010,3,12]],"date-time":"2010-03-12T13:40:30Z","timestamp":1268401230000},"page":"263-274","source":"Crossref","is-referenced-by-count":2,"title":["An Almost Linear Time Approximation Algorithm for the Permanent of a Random (0-1) Matrix"],"prefix":"10.1007","author":[{"given":"Martin","family":"F\u00fcrer","sequence":"first","affiliation":[]},{"given":"Shiva Prasad","family":"Kasiviswanathan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"22_CR1","volume-title":"Random Graphs.","author":"B. Bollob\u00e1s","year":"1985","unstructured":"Bollob\u00e1s, B.: Random Graphs. Academic Press, London (1985)"},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"Chien, S., Rasmussen, L., Sinclair, A.: Clifford algebras and approximating the permanent. In: Proceedings of the 34th ACM Symposium on Theory of Computing, pp. 222\u2013231 (2002)","DOI":"10.1145\/509907.509944"},{"key":"22_CR3","doi-asserted-by":"crossref","unstructured":"Frieze, A., Jerrum, M.: An analysis of a Monte-Carlo algorithm for approximating the permanent. Combinatorica, 67\u201383 (1995)","DOI":"10.1007\/BF01294460"},{"key":"22_CR4","doi-asserted-by":"crossref","unstructured":"Godsil, C., Gutman, I.: On the matching polynomial of a graph. Algebraic Methods in Graph Theory, 241\u2013249 (1981)","DOI":"10.1002\/jgt.3190050203"},{"key":"22_CR5","doi-asserted-by":"publisher","first-page":"1149","DOI":"10.1137\/0218077","volume":"18","author":"M. Jerrum","year":"1989","unstructured":"Jerrum, M., Sinclair, A.: Approximating the permanent. SIAM Journal of Computing\u00a018, 1149\u20131178 (1989)","journal-title":"SIAM Journal of Computing"},{"key":"22_CR6","doi-asserted-by":"crossref","unstructured":"Jerrum, M., Sinclair, A., Vigoda, E.: A polynomial time approximation algorithm for the permanent of a matrix with non-negative entries. Journal of the ACM\u00a051(4) (2004)","DOI":"10.1145\/1008731.1008738"},{"key":"22_CR7","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"M. Jerrum","year":"1986","unstructured":"Jerrum, M., Valiant, L., Vazirani, V.: Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science\u00a043, 169\u2013188 (1986)","journal-title":"Theoretical Computer Science"},{"key":"22_CR8","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1137\/0222021","volume":"22","author":"N. Karmarkar","year":"1993","unstructured":"Karmarkar, N., Karp, R., Lipton, R., Lovs\u00e1z, L., Luby, M.: A Monte-Carlo algorithm for estimating the permanent. SIAM Journal of Computing\u00a022, 284\u2013293 (1993)","journal-title":"SIAM Journal of Computing"},{"key":"22_CR9","doi-asserted-by":"publisher","first-page":"121","DOI":"10.2307\/2005469","volume":"29","author":"D.E. Knuth","year":"1974","unstructured":"Knuth, D.E.: Estimating the efficiency of backtrack programs. Mathematics of Computation\u00a029, 121\u2013136 (1974)","journal-title":"Mathematics of Computation"},{"key":"22_CR10","volume-title":"Decoupling, from Dependence to Independence","author":"V.D. Pena la","year":"1999","unstructured":"la Pena, V.D., Gin\u00e9, E.: Decoupling, from Dependence to Independence. Springer, New York (1999)"},{"key":"22_CR11","volume-title":"Permanents, Encyclopedia of Mathematics and its Applications","author":"H. Minc","year":"1982","unstructured":"Minc, H.: Permanents, Encyclopedia of Mathematics and its Applications. Addison-Wesley Publishing Company, Reading (1982)"},{"issue":"4","key":"22_CR12","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1137\/0207038","volume":"7","author":"P.W. Purdom","year":"1978","unstructured":"Purdom, P.W.: Tree size by partial backtracking. SIAM Journal on Computing\u00a07(4), 481\u2013491 (1978)","journal-title":"SIAM Journal on Computing"},{"key":"22_CR13","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1002\/rsa.3240050208","volume":"5","author":"L. Rasmussen","year":"1994","unstructured":"Rasmussen, L.: Approximating the permanent:A simple approach. Random Structures and Algorithms\u00a05, 349\u2013361 (1994)","journal-title":"Random Structures and Algorithms"},{"key":"22_CR14","volume-title":"Combinatorial Mathematics, The Carus Mathematical Monographs","author":"H. Ryser","year":"1963","unstructured":"Ryser, H.: Combinatorial Mathematics, The Carus Mathematical Monographs. The Mathematical Association of America, Washington DC (1963)"},{"issue":"4","key":"22_CR15","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1145\/234533.234534","volume":"43","author":"C. Stein","year":"1996","unstructured":"Stein, C., Karger, D.R.: A new approach to the minimum cut problem. Journal of the ACM\u00a043(4), 601\u2013640 (1996)","journal-title":"Journal of the ACM"},{"key":"22_CR16","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. Valiant","year":"1979","unstructured":"Valiant, L.: The complexity of computing the permanent. Theoretical Computer Science\u00a08, 189\u2013201 (1979)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30538-5_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T23:49:35Z","timestamp":1685490575000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30538-5_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540240587","9783540305385"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30538-5_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}