{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T03:47:32Z","timestamp":1776138452725,"version":"3.50.1"},"reference-count":46,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":5031,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[1993,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We give a randomized algorithm using<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>7<\/jats:sup>log<jats:sup>2<\/jats:sup><jats:italic>n<\/jats:italic>) separation calls to approximate the volume of a convex body with a fixed relative error. The bound is<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>6<\/jats:sup>log<jats:sup>4<\/jats:sup><jats:italic>n<\/jats:italic>) for centrally symmpetric bodies and for polytopes with a polynomial number of facets, and<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>5<\/jats:sup>log<jats:sup>4<\/jats:sup><jats:italic>n<\/jats:italic>) for centrally symmetric polytopes with a polynomial number of facets. We also give an<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>6<\/jats:sup>log<jats:italic>n<\/jats:italic>) algorithm to sample a point from the uniform distribution over a convex body. Several tools are developed that may be interesting on their own. We extend results of Sinclair\u2013Jerrum [43] and the authors [34] on the mixing rate of Markov chains from finite to arbitrary Markov chains. We also analyze the mixing rate of various random walks on convex bodies, in particular the random walk with steps from the uniform distribution over a unit ball. \u00a9 1993 John Wiley &amp; Sons, Inc.<\/jats:p>","DOI":"10.1002\/rsa.3240040402","type":"journal-article","created":{"date-parts":[[2007,5,31]],"date-time":"2007-05-31T20:51:47Z","timestamp":1180644707000},"page":"359-412","source":"Crossref","is-referenced-by-count":255,"title":["Random walks in a convex body and an improved volume algorithm"],"prefix":"10.1002","volume":"4","author":[{"given":"L.","family":"Lov\u00e1sz","sequence":"first","affiliation":[]},{"given":"M.","family":"Simonovits","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","unstructured":"N.AlonandV. D.Milman Eigenvalues expanders and superconcentrators Proc. 25th Ann. Symp. on Found. of Comput. Sci. 1984 pp.320\u2013322.","DOI":"10.1109\/SFCS.1984.715931"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90092-9"},{"key":"e_1_2_1_5_2","doi-asserted-by":"crossref","unstructured":"D.ApplegateandR.Kannan Sampling and integration of near log\u2010concave functions Proc. 23th ACM STOC 1990 pp.156\u2013163.","DOI":"10.1145\/103418.103439"},{"key":"e_1_2_1_6_2","doi-asserted-by":"crossref","unstructured":"I.B\u00e1r\u00e1nyandZ.F\u00fcredi Computing the volume is difficult Proc. 18th Ann. ACM Symp. Theory of Comput.1986 pp.442\u2013447.","DOI":"10.1145\/12130.12176"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02591694"},{"key":"e_1_2_1_8_2","volume-title":"Random Graphs","author":"Bollob\u00e1s B.","year":"1985"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-47404-0"},{"key":"e_1_2_1_10_2","doi-asserted-by":"crossref","unstructured":"G.BrightwellandP.Winkler Counting linear extenstions is # P\u2010complete Bellcore preprint 1990.","DOI":"10.1145\/103418.103441"},{"key":"e_1_2_1_11_2","doi-asserted-by":"crossref","unstructured":"A.Broder How hard is it to marry at random? (On the approximation of the permanent) Proc. 18th Ann. ACM Symp. on Theory of Comput. 1986 pp.50\u201358.","DOI":"10.1145\/12130.12136"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729330"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01899996"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01160335"},{"key":"e_1_2_1_15_2","series-title":"Pitman Res. Notes in Math. Series","first-page":"68","volume-title":"Control and Physics","author":"Dodziuk J.","year":"1986"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/0217060"},{"key":"e_1_2_1_17_2","doi-asserted-by":"crossref","unstructured":"M.DyerandA.Frieze Computing the volume of convex bodies: a case where randomness provably helps preprint 1991.","DOI":"10.1090\/psapm\/044\/1141926"},{"key":"e_1_2_1_18_2","doi-asserted-by":"crossref","unstructured":"M.DyerandA.Frieze Computing the volume of convex bodies: a case where randomness provably helps in Probabilistic Combatorics and Its Applications B\u00e9la Bollob\u00e1s Ed. Proceedings of Symposia in Applied Mathematics Vol. 44 1992 123\u2013170.","DOI":"10.1090\/psapm\/044\/1141926"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187701"},{"key":"e_1_2_1_20_2","unstructured":"U.Faigle N.Gademan andW.Kern preprint 1992."},{"key":"e_1_2_1_21_2","volume-title":"Introduction to the Theory of Probability and Its Applications, I\u2013II","author":"Feller W.","year":"1968"},{"key":"e_1_2_1_22_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2010Completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4"},{"key":"e_1_2_1_24_2","volume-title":"Measure Theory","author":"Halmos P. R.","year":"1974"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00385809"},{"key":"e_1_2_1_27_2","first-page":"216","article-title":"On the complexity of computing the volume of a polytope","volume":"3","author":"Khachiyan L. G.","year":"1988","journal-title":"Izv. Akad. Nauk SSSR, Eng. Cybern."},{"key":"e_1_2_1_28_2","first-page":"199","article-title":"The problem of computing the volume of polytopes is NP\u2010hard","volume":"44","author":"Khachiyan L. G.","year":"1989","journal-title":"Usp. Mat. Nauk."},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58043-7_5"},{"key":"e_1_2_1_30_2","article-title":"On the complexity of approximating the maximal inscribed ellipsoid for a polytope","author":"Khachiyan L. G.","journal-title":"Math. Program."},{"key":"e_1_2_1_31_2","unstructured":"J.Lawrence Polytope volume computation Preprint NISTIR 89\u20104123 US Dept. of Commerce Natl. Inst. of Stand. Tech. Gaithersburg MD."},{"key":"e_1_2_1_32_2","first-page":"538","article-title":"Integer programming with a fixed number of variables","volume":"8","author":"Lenstra H. W.","year":"1983","journal-title":"Oper. Res."},{"key":"e_1_2_1_33_2","first-page":"139","volume-title":"Proc. of Int. Congress of Math. Kyoto, 1990","author":"Lov\u00e1sz L.","year":"1991"},{"key":"e_1_2_1_34_2","first-page":"138","volume-title":"How to compute the volume? Jber. d. Dt. Math.\u2010Verein, Jubil\u00e4umstagung 1990","author":"Lov\u00e1sz L.","year":"1992"},{"key":"e_1_2_1_35_2","doi-asserted-by":"crossref","unstructured":"L.Lov\u00e1szandM.Simonovits Mixing rate of Markov chains an isoperimetric inequality and computing the volume Proc. 31st Ann. Symp. on Found. of Comput. Sci. IEEE Computer Soc. 1990 pp.346\u2013355.","DOI":"10.1109\/FSCS.1990.89553"},{"key":"e_1_2_1_36_2","doi-asserted-by":"crossref","unstructured":"L.Lov\u00e1szandM.Simonovits On the randomized complexity of volume and diameter Proc. 33rd IEEE FOCS 1992 pp.482\u2013491.","DOI":"10.1109\/SFCS.1992.267803"},{"key":"e_1_2_1_37_2","unstructured":"C. C.McGeochandA. J.Hoogs Extensions of the hit\u2010and\u2010run algorithm for random point generation(1990) (extended abstract)."},{"key":"e_1_2_1_38_2","doi-asserted-by":"publisher","DOI":"10.1063\/1.1699114"},{"key":"e_1_2_1_39_2","volume-title":"Self\u2010concordant Functions and Polynomial\u2010Time Methods in Convex Programming","author":"Nesterov A.","year":"1989"},{"key":"e_1_2_1_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00252910"},{"key":"e_1_2_1_41_2","first-page":"301","article-title":"Logarithmic concave measures with applications to stochastic programming","volume":"32","author":"Pr\u00e9kopa A.","year":"1971","journal-title":"Acta Sci. Math. Szeged."},{"key":"e_1_2_1_42_2","first-page":"335","article-title":"On logarithmic concave measures and functions","volume":"34","author":"Pr\u00e9kopa A.","year":"1973","journal-title":"Acta Sci. Math. Szeged."},{"key":"e_1_2_1_43_2","volume-title":"Functional Analysis","author":"Riesz\u2010Sz.\u2010Nagy","year":"1956"},{"key":"e_1_2_1_44_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.32.6.1296"},{"key":"e_1_2_1_45_2","doi-asserted-by":"crossref","unstructured":"A.SinclairandM.Jerrum Conductance and the rapid mixing property for Markov chains: the approximation of the permanent resolved Proc. 20th ACM STOC 1988 pp.235\u2013244.","DOI":"10.1145\/62212.62234"},{"key":"e_1_2_1_46_2","first-page":"357","article-title":"Informational complexity and efficient methods for the solution of convex extremal problems","volume":"12","author":"Yudin B. D.","journal-title":"Ekon. Mat. Metody"},{"key":"e_1_2_1_46_3","first-page":"25","volume":"13","year":"1976","journal-title":"Matekon"}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.3240040402","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.3240040402","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T20:55:35Z","timestamp":1737060935000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.3240040402"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,1]]},"references-count":46,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1993,1]]}},"alternative-id":["10.1002\/rsa.3240040402"],"URL":"https:\/\/doi.org\/10.1002\/rsa.3240040402","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,1]]}}}