A RANDOM POLYNOMIAL-TIME ALGORITHM FOR APPROXIMATING THE VOLUME OF CONVEX-BODIES

被引：326

作者：

DYER, M

FRIEZE, A

KANNAN, R

机构：

[1] UNIV LEEDS,DEPT COMP SCI,LEEDS LS2 9JT,W YORKSHIRE,ENGLAND

[2] CARNEGIE MELLON UNIV,DEPT MATH,PITTSBURGH,PA 15213

来源：

JOURNAL OF THE ACM | 1991年 / 38卷 / 01期

关键词：

ALGORITHMS; CONVEX SETS; RANDOM WALKS; SAMPLING; VOLUME;

D O I：

10.1145/102782.102783

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

A randomized polynomial-time algorithm for approximating the volume of a convex body K in n-dimensional Euclidean space is presented. The proof of correctness of the algorithm relies on recent theory of rapidly mixing Markov chains and isoperimetric inequalities to show that a certain random walk can be used to sample nearly uniformly from within K.

引用

页码：1 / 17

页数：17

共 15 条

[1]

ALDOUS D, 1983, LECT NOTES MATH, V986, P243

[2]

[Anonymous], 1988, GEOMETRIC ALGORITHMS, DOI DOI 10.1007/978-3-642-97881-4

[3]

BARANI I, 1986, 18 ANN ACM S THEOR C, P442

[4] AN ISOPERIMETRIC INEQUALITY WHICH GENERALIZES THAT OF LEVY-GROMOV,PAUL [J].