## Abstract

We present a random polynomial time algorithm for well-rounding convex bodies

Δ* ⊆

The running time is polynomial in 1/ε and

*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 language | English |
---|---|

Pages (from-to) | 117-144 |

Journal | Discrete applied mathematics |

Volume | 58 |

Issue number | 2 |

DOIs | |

Publication status | Published - 1995 |