Random walks and an O*(n5) volume algorithm for convex bodies
Random walks and an O*(n5) volume algorithm for convex bodies
复制标题
DOI：
10.1002/(sici)1098-2418(199708)11:1
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
R. Kannan;L. Lovász;M. Simonovits
中科院分区：
文献类型：
--
作者：
R. Kannan;L. Lovász;M. Simonovits
摘要通过分离甲骨文，我们可以使用O ∗（n5）呼叫来近似于相对误差ε。 ，我们使用“舍入”，然后使用多相蒙特 - 卡洛（产品估计器）技术。各向同性位置（或至少是近似值）用于舍入，•用于快速混合的全局对象（直径）和局部对象（边界问题）的分离，以及•逐步交织圆形和采样。
Abstract Given a high dimensional convex body K ⊆ IR by a separation oracle, we can approximate its volume with relative error ε, using O∗(n5) oracle calls. Our algorithm also brings the body into isotropic position. As all previous randomized volume algorithms, we use “rounding” followed by a multiphase Monte-Carlo (product estimator) technique. Both parts rely on sampling (generating random points in K), which is done by random walk. Our algorithm introduces three new ideas: • the use of the isotropic position (or at least an approximation of it) for rounding, • the separation of global obstructions (diameter) and local obstructions (boundary problems) for fast mixing, and • a stepwise interlacing of rounding and sampling.