{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:16:46Z","timestamp":1725560206402},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540200642"},{"type":"electronic","value":"9783540396581"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-39658-1_66","type":"book-chapter","created":{"date-parts":[[2010,7,22]],"date-time":"2010-07-22T23:24:30Z","timestamp":1279841070000},"page":"740-751","source":"Crossref","is-referenced-by-count":0,"title":["Multisampling: A New Approach to Uniform Sampling and Approximate Counting"],"prefix":"10.1007","author":[{"given":"Piotr","family":"Sankowski","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"66_CR1","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1002\/(SICI)1098-2418(1999010)14:1<29::AID-RSA2>3.0.CO;2-X","volume":"14","author":"A. Barvinok","year":"1999","unstructured":"Barvinok, A.: Polynomial time algorithms to approximate permanents and mixed discriminants within a simply exponential factor. Random Structures and Algorithms\u00a014, 29\u201361 (1999)","journal-title":"Random Structures and Algorithms"},{"key":"66_CR2","unstructured":"Barvinok, A.: New Permanent Estimators Via Non-Commutative Determinants (preprint)"},{"key":"66_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jcph.1998.6149","volume":"149","author":"I. Beichl","year":"1999","unstructured":"Beichl, I., Sullivan, F.: Approximating the Permanent via Importance Sampling with Application to Dimer Covering Problem. Journal of computational Physics\u00a0149, 1 (1999)","journal-title":"Journal of computational Physics"},{"key":"66_CR4","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. 712\u2013721 (2001)","DOI":"10.1145\/509907.509944"},{"key":"66_CR5","unstructured":"Dyer, M., Greenhill, C.: On Markov Chains for independent sets (1997) (preprint)"},{"key":"66_CR6","doi-asserted-by":"crossref","unstructured":"Feder, T., Mihail, M.: Balanced matroids. In: Proceedings of the 24th Annual ACM Symposium on the theory of Computing (STOC), pp. 26\u201338 (1992)","DOI":"10.1145\/129712.129716"},{"key":"66_CR7","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/BF01294460","volume":"15","author":"A. Frieze","year":"1995","unstructured":"Frieze, A., Jerrum, M.: An analysis of a Monte Carlo algorithm for estimating the permanent. Combinatorica\u00a015, 67\u201383 (1995)","journal-title":"Combinatorica"},{"key":"66_CR8","first-page":"241","volume-title":"Algebraic Methods in Graph Theory","author":"C.D. Godsil","year":"1981","unstructured":"Godsil, C.D., Gutman, I.: On the matching polynomial of a graph. In: Algebraic Methods in Graph Theory, Szeged (1978), vol.\u00a0I, II, pp. 241\u2013249. North-Holland, Amsterdam (1981)"},{"key":"66_CR9","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 on Computing\u00a018, 1149\u20131178 (1989)","journal-title":"SIAM Journal on Computing"},{"key":"66_CR10","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1137\/0222066","volume":"22","author":"M. Jerrum","year":"1993","unstructured":"Jerrum, M., Sinclair, A.: Polynomial-time Approximation Algorithms for the Ising Model. SIAM Journal on Computing\u00a022, 1087\u20131116 (1993)","journal-title":"SIAM Journal on Computing"},{"key":"66_CR11","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1002\/rsa.3240070205","volume":"7","author":"M. Jerrum","year":"1995","unstructured":"Jerrum, M.: A very simple algorithm for estimating the number of k-colorings of a low-degree graph. Random Structures and Algorithms\u00a07, 157\u2013165 (1995)","journal-title":"Random Structures and Algorithms"},{"key":"66_CR12","unstructured":"Jerrum, M., Sinclair, A.: The Markov Chain Monte Carlo method: an approach to approximate counting and integration. In: Hochbaum, D. (ed.) Approximation Algorithms for NP-hard Problems. PWS (1996)"},{"key":"66_CR13","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. In: STOC (2000)","DOI":"10.1145\/380752.380877"},{"key":"66_CR14","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., Lov\u00e1sz, L., Luby, M.: A Monte Carlo algorithm for estimating the permanent. SIAM Journal on Computing\u00a022, 284\u2013293 (1993)","journal-title":"SIAM Journal on Computing"},{"key":"66_CR15","doi-asserted-by":"crossref","unstructured":"Kaltofen, E., Villard, G.: On the complexity of computing determinants. In: Proc. Fifth Asian Symposium on Computer Mathematics (ASCM 2001), Singapore. Lecture Notes Series on Computing, vol.\u00a09, pp. 13\u201327 (2001)","DOI":"10.1142\/9789812799661_0002"},{"key":"66_CR16","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1002\/rsa.3240050208","volume":"5","author":"L.E. Rasmussen","year":"1994","unstructured":"Rasmussen, L.E.: Approximating the Permanent: a Simple Approach. Random Structures Algorithms\u00a05, 349\u2013361 (1994)","journal-title":"Random Structures Algorithms"},{"key":"66_CR17","unstructured":"Morris, B., Sinclair, A.: Random Walks on Truncated Cubes and Sampling 0\u22121 Kanpsack Solutions. In: Proceedings of the 40th IEEE Symposium on Fundations of Computer Science (FOCS), pp. 203\u2013240 (1999)"},{"key":"66_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/3-540-36494-3_38","volume-title":"STACS 2003","author":"P. Sankowski","year":"2003","unstructured":"Sankowski, P.: Alternative Algorithm for Counting All Matchings in Graphs. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol.\u00a02607, pp. 427\u2013438. Springer, Heidelberg (2003)"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2003"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-39658-1_66","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,1]],"date-time":"2021-11-01T04:57:47Z","timestamp":1635742667000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-39658-1_66"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540200642","9783540396581"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-39658-1_66","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}