A random polynomial time algorithm for well-rounding convex bodies

0.00 Avg rating—0 Votes

Article ID:	iaor19971035
Country:	Netherlands
Volume:	58
Issue:	2
Start Page Number:	117
End Page Number:	144
Publication Date:	Mar 1995
Journal:	Discrete Applied Mathematics
Authors:	Faigle U., Kern W., Gademann N.
Keywords:	computational analysis

Abstract:

The authors present a random polynomial time algorithm for well-rounding convex bodies K in the following sense: Given K⊆ℝⁿ and •>0, the algorithm, with probability at least 1-•, computes two simplices ℝ* and ℝ**, where ℝ** is the blow up of ℝ* from its center by a factor of n+3, such that ℝ*⊆K and vol(Kz.drule;ℝ**)•• volK. The running time is polynomial in 1/• and L, the size of the input K.

Reviews

Required fields are marked *. Your email address will not be published.