{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T00:54:38Z","timestamp":1743036878483,"version":"3.40.3"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319130743"},{"type":"electronic","value":"9783319130750"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-13075-0_30","type":"book-chapter","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T16:37:06Z","timestamp":1415983026000},"page":"376-386","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An FPTAS for the Volume Computationof 0-1 Knapsack Polytopes Based on Approximate Convolution Integral"],"prefix":"10.1007","author":[{"given":"Ei","family":"Ando","sequence":"first","affiliation":[]},{"given":"Shuji","family":"Kijima","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,11,8]]},"reference":[{"key":"30_CR1","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1002\/rsa.20236","volume":"33","author":"A Bandyopadhyay","year":"2008","unstructured":"Bandyopadhyay, A., Gamarnik, D.: Counting without sampling: asymptotics of the log-partition function for certain statistical physics models. Random Structures and Algorithms 33, 452\u2013479 (2008)","journal-title":"Random Structures and Algorithms"},{"key":"30_CR2","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/BF02187886","volume":"2","author":"I B\u00e1r\u00e1ny","year":"1987","unstructured":"B\u00e1r\u00e1ny, I., F\u00fcredi, Z.: Computing the volume is difficult. Discrete Computational Geometry 2, 319\u2013326 (1987)","journal-title":"Discrete Computational Geometry"},{"key":"30_CR3","doi-asserted-by":"crossref","unstructured":"Bayati, M., Gamarnik, D., Katz, D., Nair, C., Tetali, P.: Simple deterministic approximation algorithms for counting matchings. In: Proc. of STOC 2007, pp. 122\u2013127 (2007)","DOI":"10.1145\/1250790.1250809"},{"key":"30_CR4","doi-asserted-by":"crossref","unstructured":"Dyer, M.: Approximate counting by dynamic programming. In: Proc. of STOC 2003, pp. 693\u2013699 (2003)","DOI":"10.1145\/780542.780643"},{"issue":"5","key":"30_CR5","doi-asserted-by":"publisher","first-page":"967","DOI":"10.1137\/0217060","volume":"17","author":"M Dyer","year":"1988","unstructured":"Dyer, M., Frieze, A.: On the complexity of computing the volume of a polyhedron. SIAM Journal on Computing 17(5), 967\u2013974 (1988)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"30_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/102782.102783","volume":"38","author":"M Dyer","year":"1991","unstructured":"Dyer, M., Frieze, A., Kannan, R.: A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the Association for Computing Machinery 38(1), 1\u201317 (1991)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"30_CR7","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/BF02187701","volume":"1","author":"G Elekes","year":"1986","unstructured":"Elekes, G.: A geometric inequality and the complexity of computing volume. Discrete Computational Geometry 1, 289\u2013292 (1986)","journal-title":"Discrete Computational Geometry"},{"key":"30_CR8","unstructured":"Gamarnik, D., Katz, D.: Correlation decay and deterministic FPTAS for counting list-colorings of a graph. In: Proc. of SODA 2007, pp. 1245\u20131254 (2007)"},{"key":"30_CR9","doi-asserted-by":"crossref","unstructured":"Gopalan, P., Klivans, A., Meka, R.: Polynomial-time approximation schemes for knapsack and related counting problems using branching programs, arXiv:1008.3187v1 (2010)","DOI":"10.1109\/FOCS.2011.32"},{"key":"30_CR10","doi-asserted-by":"crossref","unstructured":"Gopalan, P., Klivans, A., Meka, R., \u0160tefankovi\u010d, D., Vempala, S., Vigoda, E.: An FPTAS for #knapsack and related counting problems. In: Proc. of FOCS 2011, pp. 817\u2013826 (2011)","DOI":"10.1109\/FOCS.2011.32"},{"key":"30_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-6802-1","volume-title":"Complexity Theory of Real Functions","author":"K-I Ko","year":"1991","unstructured":"Ko, K.-I.: Complexity Theory of Real Functions. Birkh\u00e4user, Boston (1991)"},{"key":"30_CR12","doi-asserted-by":"crossref","unstructured":"Li, L., Lu, P., Yin, Y.: Approximate counting via correlation decay in spin systems. In: Proc. of SODA 2012, pp. 922\u2013940 (2012)","DOI":"10.1137\/1.9781611973099.74"},{"key":"30_CR13","doi-asserted-by":"crossref","unstructured":"Li, L., Lu, P., Yin, Y.: Correlation decay up to uniqueness in spin systems. In: Proc. of SODA 2013, pp. 67\u201384 (2013)","DOI":"10.1137\/1.9781611973105.5"},{"key":"30_CR14","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/j.orl.2014.02.004","volume":"42","author":"J Li","year":"2014","unstructured":"Li, J., Shi, T.: A fully polynomial-time approximation scheme for approximating a sum of random variables. Operations Research Letters 42, 197\u2013202 (2014)","journal-title":"Operations Research Letters"},{"key":"30_CR15","doi-asserted-by":"crossref","unstructured":"Lin, C., Liu, J., Lu, P.: A simple FPTAS for counting edge covers. In: Proc. of SODA 2014, pp. 341\u2013348 (2014)","DOI":"10.1137\/1.9781611973402.25"},{"key":"30_CR16","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L.: An Algorithmic Theory of Numbers, Graphs and Convexity. SIAM Society for industrial and applied mathematics, Philadelphia (1986)","DOI":"10.1137\/1.9781611970203"},{"key":"30_CR17","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1016\/j.jcss.2005.08.004","volume":"72","author":"L Lov\u00e1sz","year":"2006","unstructured":"Lov\u00e1sz, L., Vempala, S.: Simulated annealing in convex bodies and an $$O^\\ast (n^4)$$ volume algorithm. Journal of Computer and System Sciences 72, 392\u2013417 (2006)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"30_CR18","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1137\/0120026","volume":"20","author":"S Mitra","year":"1971","unstructured":"Mitra, S.: On the probability distribution of the sum of uniformly distributed random variables. SIAM Journal on Applied Mathematics 20(2), 195\u2013198 (1971)","journal-title":"SIAM Journal on Applied Mathematics"},{"issue":"2","key":"30_CR19","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1137\/11083976X","volume":"41","author":"D \u0160tefankovi\u010d","year":"2012","unstructured":"\u0160tefankovi\u010d, D., Vempala, S., Vigoda, E.: A deterministic polynomial-time approximation scheme for counting knapsack solutions. SIAM Journal on Computing 41(2), 356\u2013366 (2012)","journal-title":"SIAM Journal on Computing"},{"key":"30_CR20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-56999-9","volume-title":"Computable Analysis An Introduction","author":"K Weihrauch","year":"2000","unstructured":"Weihrauch, K.: Computable Analysis An Introduction. Springer, Berlin (2000)"},{"key":"30_CR21","doi-asserted-by":"crossref","unstructured":"Weitz, D.: Counting independent sets up to the tree threshold. In: Proc. STOC 2006, pp. 140\u2013149 (2006)","DOI":"10.1145\/1132516.1132538"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-13075-0_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,15]],"date-time":"2023-02-15T00:12:57Z","timestamp":1676419977000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-13075-0_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319130743","9783319130750"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-13075-0_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"8 November 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}