A random polynomial time algorithm for well-rounding convex bodies

Faigle, U. and Gademann, N. and Kern, W. (1995) A random polynomial time algorithm for well-rounding convex bodies. Discrete Applied Mathematics, 58 (2). pp. 117-144. ISSN 0166-218X

Preview

PDF
1540Kb

Abstract:	We 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 (K/Δ*)≤ volK. The running time is polynomial in 1 / and L, the size of the input K.
Item Type:	Article
Copyright:	© 1995 Elsevier Science
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/30047
Official URL:	http://dx.doi.org/10.1016/0166-218X(93)E0123-G
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 140686