Rounding of Polytopes in the Real Number Model of Computation
Leonid G. Khachiyan Β· Mathematics of Operations Research Β· 1996
Let π be a set of m points in β n . We show that the problem of (1 + Ο΅)n-rounding of π, i.e., the problem of computing an ellipsoid E β β n such that [(1 + Ο΅)n] β1 E β conv. hull(π) β E, can be solved in O(mn 2 (Ο΅ β1 + ln n + ln ln m)) arithmetic operations and comparisons. This result implies that the problem of approximating the minimum volume ellipsoid circumscribed about π can be solved in O(m 3.5 ln(mΟ΅ β1 )) operations to a relative accuracy of Ο΅ in the volume. The latter bound also applies to the (1 + Ο΅)n-rounding problem. Our bounds hold for the real number model of computation.