Simulated annealing in convex bodies and an O*(n4) volume algorithm

被引：124

作者：

Lovász, L

Vempala, S

机构：

[1] MIT, Dept Math, Cambridge, MA 02139 USA

[2] Microsoft Res, Redmond, WA 98052 USA

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 2006年 / 72卷 / 02期

基金：

美国国家科学基金会;

关键词：

convex bodies; volume computation; random walks; simulated annealing; logconcave functions;

D O I：

10.1016/j.jcss.2005.08.004

中图分类号：

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

学科分类号：

0812 ;

摘要：

We present a new algorithm for computing the volume of a convex body in R-n. The main ingredients of the algorithm are (i) a "morphing" technique that can be viewed as a variant of simulated annealing and (ii) a new rounding algorithm to put a convex body in near-isotropic position. The complexity is O*(n(4)), improving on the previous best algorithm by a factor of n. (c) 2005 Elsevier Inc. All rights reserved.

引用

页码：392 / 417

页数：26

共 23 条

[1]

Applegate D., 1990, P 23 ACM STOC, P156

[2] COMPUTING THE VOLUME IS DIFFICULT [J].