A random polynomial time algorithm for well-rounding convex bodies

U. Faigle, N. Gademann, W. Kern

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
97 Downloads (Pure)

Abstract

We present a random polynomial time algorithm for well-rounding convex bodies K in the following sense: Given K ⊆ ℜn 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/Δ**) ≤ vol K.

The running time is polynomial in 1/ε and L, the size of the input K.
Original languageEnglish
Pages (from-to)117-144
JournalDiscrete applied mathematics
Volume58
Issue number2
DOIs
Publication statusPublished - 1995

Fingerprint

Dive into the research topics of 'A random polynomial time algorithm for well-rounding convex bodies'. Together they form a unique fingerprint.

Cite this