A random polynomial time algorithm for well-rounding convex bodies

Share/Save/Bookmark

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

open access
[img]
Preview
PDF
1MB
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:
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

 

Repository Staff Only: item control page

Metis ID: 140686