{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T01:02:34Z","timestamp":1773363754743,"version":"3.50.1"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2009,5,1]],"date-time":"2009-05-01T00:00:00Z","timestamp":1241136000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0455666"],"award-info":[{"award-number":["CCF-0455666"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0721503"],"award-info":[{"award-number":["CCF-0721503"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,5]]},"abstract":"\n We present a near-optimal reduction from approximately counting the cardinality of a discrete set to approximately sampling elements of the set. An important application of our work is to approximating the partition function\n Z<\/jats:italic>\n of a discrete system, such as the Ising model, matchings or colorings of a graph. The typical approach to estimating the partition function\n Z<\/jats:italic>\n (\u03b2\n *<\/jats:sup>\n ) at some desired inverse temperature \u03b2\n *<\/jats:sup>\n is to define a sequence, which we call a\n cooling schedule<\/jats:italic>\n , \u03b2\n 0<\/jats:sub>\n = 0 < \u03b2\n 1<\/jats:sub>\n < \u2026 < \u03b2\n \u2113<\/jats:sub>\n = \u03b2\n *<\/jats:sup>\n where\n Z(0)<\/jats:italic>\n is trivial to compute and the ratios\n Z<\/jats:italic>\n (\u03b2\n \n i<\/jats:italic>\n +1\n <\/jats:sub>\n )\/\n Z<\/jats:italic>\n (\u03b2\n \n i<\/jats:italic>\n <\/jats:sub>\n ) are easy to estimate by sampling from the distribution corresponding to\n Z<\/jats:italic>\n (\u03b2\n \n i<\/jats:italic>\n <\/jats:sub>\n ). Previous approaches required a cooling schedule of length\n O<\/jats:italic>\n *<\/jats:sup>\n (ln\n A<\/jats:italic>\n ) where\n A<\/jats:italic>\n =\n Z<\/jats:italic>\n (0), thereby ensuring that each ratio\n Z<\/jats:italic>\n (\u03b2\n \n i<\/jats:italic>\n +1\n <\/jats:sub>\n )\/\n Z<\/jats:italic>\n (\u03b2\n \n i<\/jats:italic>\n <\/jats:sub>\n ) is bounded. We present a cooling schedule of length \u2113 =\n O<\/jats:italic>\n *<\/jats:sup>\n (\u221a ln\n A<\/jats:italic>\n ).\n <\/jats:p>\n \n For well-studied problems such as estimating the partition function of the Ising model, or approximating the number of colorings or matchings of a graph, our cooling schedule is of length\n O<\/jats:italic>\n *<\/jats:sup>\n (\u221a\n n<\/jats:italic>\n ), which implies an overall savings of\n O<\/jats:italic>\n *<\/jats:sup>\n (\n n<\/jats:italic>\n ) in the running time of the approximate counting algorithm (since roughly \u2113 samples are needed to estimate each ratio).\n <\/jats:p>\n \n A similar improvement in the length of the cooling schedule was recently obtained by Lov\u00e1sz and Vempala in the context of estimating the volume of convex bodies. While our reduction is inspired by theirs, the discrete analogue of their result turns out to be significantly more difficult. Whereas a fixed schedule suffices in their setting, we prove that in the discrete setting we need an adaptive schedule, that is, the schedule depends on\n Z<\/jats:italic>\n . More precisely, we prove any nonadaptive cooling schedule has length at least\n O<\/jats:italic>\n *<\/jats:sup>\n (ln\n A<\/jats:italic>\n ), and we present an algorithm to find an adaptive schedule of length\n O<\/jats:italic>\n *<\/jats:sup>\n (\u221a ln\n A<\/jats:italic>\n ).\n <\/jats:p>","DOI":"10.1145\/1516512.1516520","type":"journal-article","created":{"date-parts":[[2009,5,19]],"date-time":"2009-05-19T16:47:42Z","timestamp":1242751662000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":52,"title":["Adaptive simulated annealing: A near-optimal connection between sampling and counting"],"prefix":"10.1145","volume":"56","author":[{"given":"Daniel","family":"\u0160tefankovi\u010d","sequence":"first","affiliation":[{"name":"University of Rochester, Rochester, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Santosh","family":"Vempala","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Vigoda","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,5,19]]},"reference":[{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/050644033"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of Symposiusm on Applied Mathematics","volume":"44","author":"Dyer M.","unstructured":"Dyer , M. , and Frieze , A . 1991. Computing the volume of convex bodies: a case where randomness provably helps. In Probabilistic combinatorics and its applications . Proceedings of Symposiusm on Applied Mathematics , vol. 44 . American Mathematics Society, Providence, RI, 123--169. Dyer, M., and Frieze, A. 1991. Computing the volume of convex bodies: a case where randomness provably helps. In Probabilistic combinatorics and its applications. Proceedings of Symposiusm on Applied Mathematics, vol. 44. American Mathematics Society, Providence, RI, 123--169."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102783"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.61.2635"},{"key":"e_1_2_1_6_1","volume-title":"Oxford Lecture Ser. Math. Appl.","volume":"34","author":"Frieze A.","unstructured":"Frieze , A. , and Vigoda , E . 2007. A survey on the use of Markov chains to randomly sample colourings. In Combinatorics, complexity, and chance . Oxford Lecture Ser. Math. Appl. , vol. 34 . Oxford Univ. Press, Oxford, UK, 53--71. Frieze, A., and Vigoda, E. 2007. A survey on the use of Markov chains to randomly sample colourings. In Combinatorics, complexity, and chance. Oxford Lecture Ser. Math. Appl., vol. 34. Oxford Univ. Press, Oxford, UK, 53--71."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794268765"},{"key":"e_1_2_1_8_1","unstructured":"Janson S. Luczak T. and Rucinski A. 2000. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience New York. Janson S. Luczak T. and Rucinski A. 2000. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience New York."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070205"},{"key":"e_1_2_1_10_1","volume-title":"sampling and integrating: algorithms and complexity. Lectures in Mathematics ETH Z\u00fcrich","author":"Jerrum M.","unstructured":"Jerrum , M. 2003. Counting , sampling and integrating: algorithms and complexity. Lectures in Mathematics ETH Z\u00fcrich . Birkh\u00e4user Verlag , Basel . Jerrum, M. 2003. Counting, sampling and integrating: algorithms and complexity. Lectures in Mathematics ETH Z\u00fcrich. Birkh\u00e4user Verlag, Basel."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008738"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/11534.11537"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199708)11:1%3C1::AID-RSA1%3E3.0.CO;2-X"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.28"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.08.004"},{"key":"e_1_2_1_17_1","volume-title":"Probability on Discrete Structures. Encyclopaedia Math. Sci.","author":"Martinelli F.","unstructured":"Martinelli , F. 2004. Relaxation times of Markov chains in statistical mechanics and combinatorial structures . In Probability on Discrete Structures. Encyclopaedia Math. Sci. , vol. 110 . Springer-Verlag , Berlin, Germany , 175--262. Martinelli, F. 2004. Relaxation times of Markov chains in statistical mechanics and combinatorial structures. In Probability on Discrete Structures. Encyclopaedia Math. Sci., vol. 110. Springer-Verlag, Berlin, Germany, 175--262."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02101929"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1729945"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1678245"},{"key":"e_1_2_1_21_1","volume-title":"Combinatorial and computational geometry. Math. Sci. Res. Inst. Publ.","author":"Vempala S.","unstructured":"Vempala , S. 2005. Geometric random walks: A survey . In Combinatorial and computational geometry. Math. Sci. Res. Inst. Publ. , vol. 52 . Cambridge Univ. Press , Cambridge, MA , 577--616. Vempala, S. 2005. Geometric random walks: A survey. In Combinatorial and computational geometry. Math. Sci. Res. Inst. Publ., vol. 52. Cambridge Univ. Press, Cambridge, MA, 577--616."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.37236\/1552"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132538"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1516512.1516520","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1516512.1516520","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:06Z","timestamp":1750253406000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1516512.1516520"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,5]]}},"alternative-id":["10.1145\/1516512.1516520"],"URL":"https:\/\/doi.org\/10.1145\/1516512.1516520","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,5]]},"assertion":[{"value":"2007-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-05-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}