{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T16:27:43Z","timestamp":1743006463670,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319623887"},{"type":"electronic","value":"9783319623894"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-62389-4_2","type":"book-chapter","created":{"date-parts":[[2017,6,30]],"date-time":"2017-06-30T15:07:46Z","timestamp":1498835266000},"page":"13-24","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An FPTAS for the Volume of Some $$\\mathcal{V}$$-polytopes\u2014It is Hard to Compute the Volume of the Intersection of Two Cross-Polytopes"],"prefix":"10.1007","author":[{"given":"Ei","family":"Ando","sequence":"first","affiliation":[]},{"given":"Shuji","family":"Kijima","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,7,1]]},"reference":[{"issue":"4","key":"2_CR1","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1007\/s00453-015-0096-5","volume":"76","author":"E Ando","year":"2016","unstructured":"Ando, E., Kijima, S.: An FPTAS for the volume computation of 0\u20131 knapsack polytopes based on approximate convolution. Algorithmica 76(4), 1245\u20131263 (2016)","journal-title":"Algorithmica"},{"key":"2_CR2","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 Struct. Algorithms 33, 452\u2013479 (2008)","journal-title":"Random Struct. Algorithms"},{"key":"2_CR3","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 Comput. Geom. 2, 319\u2013326 (1987)","journal-title":"Discrete Comput. Geom."},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"Bayati, M., Gamarnik, D., Katz, D., Nair, C., Tetali, P.: Simple deterministic approximation algorithms for counting matchings. In: Proceedings of STOC 2007, pp. 122\u2013127 (2007)","DOI":"10.1145\/1250790.1250809"},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"Cousins, B., Vempala, S., Bypassing, K.L.S.: Gaussian cooling and an $$O^\\ast (n^3)$$ volume algorithm. In: Proceedings of STOC 2015, pp. 539\u2013548 (2015)","DOI":"10.1145\/2746539.2746563"},{"issue":"48","key":"2_CR6","doi-asserted-by":"publisher","first-page":"19237","DOI":"10.1073\/pnas.1203863110","volume":"110","author":"D Dadush","year":"2013","unstructured":"Dadush, D., Vempala, S.: Near-optimal deterministic algorithms for volume computation via M-ellipsoids. Proc. Natl. Acad. Sci. USA 110(48), 19237\u201319245 (2013)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"Dyer, M.: Approximate counting by dynamic programming. In: Proceedings of STOC 2003, pp. 693\u2013699 (2003)","DOI":"10.1145\/780542.780643"},{"issue":"5","key":"2_CR8","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 J. Comput. 17(5), 967\u2013974 (1988)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"2_CR9","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. J. Assoc. Comput. Mach. 38(1), 1\u201317 (1991)","journal-title":"J. Assoc. Comput. Mach."},{"key":"2_CR10","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 Comput. Geom. 1, 289\u2013292 (1986)","journal-title":"Discrete Comput. Geom."},{"key":"2_CR11","unstructured":"Gamarnik, D., Katz, D.: Correlation decay and deterministic FPTAS for counting list-colorings of a graph. In: Proceedings of SODA 2007, pp. 1245\u20131254 (2007)"},{"key":"2_CR12","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":"2_CR13","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: Proceedings of FOCS 2011, pp. 817\u2013826 (2011)","DOI":"10.1109\/FOCS.2011.32"},{"key":"2_CR14","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R Karp","year":"1972","unstructured":"Karp, R.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"2_CR15","first-page":"199","volume":"44","author":"L Khachiyan","year":"1989","unstructured":"Khachiyan, L.: The problem of computing the volume of polytopes is $$\\#P$$-hard. Uspekhi Mat. Nauk. 44, 199\u2013200 (1989)","journal-title":"Uspekhi Mat. Nauk."},{"key":"2_CR16","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/978-3-642-58043-7_5","volume-title":"New Trends in Discrete and Computational Geometry","author":"L Khachiyan","year":"1993","unstructured":"Khachiyan, L.: Complexity of polytope volume computation. In: Pach, J. (ed.) New Trends in Discrete and Computational Geometry, pp. 91\u2013101. Springer, Berlin (1993)"},{"key":"2_CR17","doi-asserted-by":"crossref","unstructured":"Li, L., Lu, P., Yin, Y.: Approximate counting via correlation decay in spin systems. In: Proceedings of SODA 2012, pp. 922\u2013940 (2012)","DOI":"10.1137\/1.9781611973099.74"},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"Li, L., Lu, P., Yin, Y.: Correlation decay up to uniqueness in spin systems. In: Proceedings of SODA 2013, pp. 67\u201384 (2013)","DOI":"10.1137\/1.9781611973105.5"},{"key":"2_CR19","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. Oper. Res. Lett. 42, 197\u2013202 (2014)","journal-title":"Oper. Res. Lett."},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"Lin, C., Liu, J., Lu, P.: A simple FPTAS for counting edge covers. In: Proceedings of SODA 2014, pp. 341\u2013348 (2014)","DOI":"10.1137\/1.9781611973402.25"},{"key":"2_CR21","series-title":"Applied Mathematics","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970203","volume-title":"An Algorithmic Theory of Numbers, Graphs and Convexity","author":"L Lov\u00e1sz","year":"1986","unstructured":"Lov\u00e1sz, L.: An Algorithmic Theory of Numbers, Graphs and Convexity. Applied Mathematics. SIAM Society for Industrial, Philadelphia (1986)"},{"key":"2_CR22","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. J. Comput. Syst. Sci. 72, 392\u2013417 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"J Matous\u0306ek","year":"2002","unstructured":"Matous\u0306ek, J.: Lectures on Discrete Geometry. Springer, New York (2002)"},{"issue":"2","key":"2_CR24","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 J. Comput. 41(2), 356\u2013366 (2012)","journal-title":"SIAM J. Comput."},{"key":"2_CR25","doi-asserted-by":"crossref","unstructured":"Weitz, D.: Counting independent sets up to the tree threshold. In: Proceedings of STOC 2006, pp. 140\u2013149 (2006)","DOI":"10.1145\/1132516.1132538"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-62389-4_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T11:22:48Z","timestamp":1709810568000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-62389-4_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319623887","9783319623894"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-62389-4_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"1 July 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hong Kong","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 August 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 August 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cocoon2017.comp.polyu.edu.hk\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}