{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T03:16:03Z","timestamp":1790824563808,"version":"4.1.0"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319196466","type":"print"},{"value":"9783319196473","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-319-19647-3_6","type":"book-chapter","created":{"date-parts":[[2015,6,26]],"date-time":"2015-06-26T09:03:08Z","timestamp":1435309388000},"page":"52-65","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["A Fast and Practical Method to Estimate Volumes of Convex Polytopes"],"prefix":"10.1007","author":[{"given":"Cunjing","family":"Ge","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Feifei","family":"Ma","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,6,27]]},"reference":[{"issue":"5","key":"6_CR1","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."},{"key":"6_CR2","first-page":"216","volume":"3","author":"LG Khachiyan","year":"1988","unstructured":"Khachiyan, L.G.: On the complexity of computing the volume of a polytope. Izvestia Akad. Nauk SSSR Tekhn. Kibernet 3, 216\u2013217 (1988)","journal-title":"Izvestia Akad. Nauk SSSR Tekhn. Kibernet"},{"key":"6_CR3","first-page":"179","volume":"44","author":"LG Khachiyan","year":"1989","unstructured":"Khachiyan, L.G.: The problem of computing the volume of polytopes is NP-hard. Uspekhi Mat. Nauk. 44, 179\u2013180 (1989). In Russian; translation in. Russian Math. Surv. 44(3), 199\u2013200","journal-title":"Uspekhi Mat. Nauk."},{"key":"6_CR4","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/978-3-0348-8438-9_6","volume-title":"Polytopes\u2014Combinatorics and Computation","author":"B B\u00fceler","year":"2000","unstructured":"B\u00fceler, B., Enge, A., Fukuda, K.: Exact volume computation for polytopes: a practical study. In: Kalai, G., Ziegler, G.M. (eds.) Polytopes\u2014Combinatorics and Computation, pp. 131\u2013154. Birkh\u00e4user Verlag, Birkh\u00e4user Basel (2000)"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Dyer, M., Frieze, A., Kannan, R.: A random polynomial time algorithm for approximating the volume of convex bodies. In: 21st Annual ACM Symposium on Theory of Computing, pp. 375\u2013381 (1989)","DOI":"10.1145\/73007.73043"},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L., Simonovits M.: Mixing rate of Markov chains, an isoperimetric inequality, and computing a the volume. In: 31st Annual Symposium on Foundations of Computer Science, Vol. I, II, pp. 346\u2013354 (1990)","DOI":"10.1109\/FSCS.1990.89553"},{"issue":"1","key":"6_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO;2-X","volume":"11","author":"R Kannan","year":"1997","unstructured":"Kannan, R., Lov\u00e1sz, L., Simonovits, M.: Random walks and an $$O^*(n^5)$$ volume algorithm for convex bodies. Random Struct. Algorithms 11(1), 1\u201350 (1997)","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"6_CR8","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/s101070050099","volume":"86","author":"L Lov\u00e1sz","year":"1999","unstructured":"Lov\u00e1sz, L.: Hit-and-Run mixes fast. Math. Prog. 86(3), 443\u2013461 (1999)","journal-title":"Math. Prog."},{"issue":"2","key":"6_CR9","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^*(n^4)$$ volume algorithm. J. Comput. Syst. Sci. 72(2), 392\u2013417 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR10","unstructured":"http:\/\/www.math.u-bordeaux1.fr\/aenge\/?category=software&page=vinci"},{"key":"6_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"1993","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Heidelberg (1993)"},{"issue":"1","key":"6_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01583776","volume":"23","author":"D Goldfarb","year":"1982","unstructured":"Goldfarb, D., Todd, M.J.: Modifications and implementation of the ellipsoid algorithm for linear programming. Math. Program. 23(1), 1\u201319 (1982)","journal-title":"Math. Program."},{"key":"6_CR13","doi-asserted-by":"publisher","first-page":"1296","DOI":"10.1287\/opre.32.6.1296","volume":"32","author":"RL Smith","year":"1984","unstructured":"Smith, R.L.: Efficient Monte-Carlo procedures for generating points uniformly distributed over bounded regions. Oper. Res. 32, 1296\u20131308 (1984)","journal-title":"Oper. Res."},{"issue":"2","key":"6_CR14","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1007\/BF02591694","volume":"37","author":"HCP Berbee","year":"1987","unstructured":"Berbee, H.C.P., Boender, C.G.E., Ran, A.R., Scheffer, C.L., Smith, R.L., Telgen, J.: Hit-and-run algorithms for the identification of nonredundant linear inequalities. Math. Program. 37(2), 184\u2013207 (1987)","journal-title":"Math. Program."},{"issue":"2","key":"6_CR15","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1287\/moor.18.2.255","volume":"18","author":"CJP Belisle","year":"1993","unstructured":"Belisle, C.J.P., Romeijn, H.E., Smith, R.L.: Hit-and-run algorithms for generating multivariate distributions. Math. Oper. Res. 18(2), 255\u2013266 (1993)","journal-title":"Math. Oper. Res."},{"key":"6_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1007\/978-3-540-73545-8_21","volume-title":"Computing and Combinatorics","author":"S Liu","year":"2007","unstructured":"Liu, S., Zhang, J., Zhu, B.: Volume computation using a direct Monte Carlo method. In: Lin, G. (ed.) COCOON 2007. LNCS, vol. 4598, pp. 198\u2013209. Springer, Heidelberg (2007)"},{"key":"6_CR17","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1016\/j.ejor.2011.06.024","volume":"216","author":"L Lov\u00e1sz","year":"2012","unstructured":"Lov\u00e1sz, L., De\u00e1k, I.: Computational results of an $$O^*(n^4)$$ volume algorithm. Eur. J. Oper. Res. 216, 152\u2013161 (2012)","journal-title":"Eur. J. Oper. Res."}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-19647-3_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T21:48:12Z","timestamp":1748468892000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-19647-3_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319196466","9783319196473"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19647-3_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"27 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}