Rounding of polytopes in the real number model of computation

Rounding of polytopes in the real number model of computation

0.00 Avg rating0 Votes
Article ID: iaor20041210
Country: United States
Volume: 21
Issue: 2
Start Page Number: 307
End Page Number: 320
Publication Date: May 1996
Journal: Mathematics of Operations Research
Authors:
Abstract:

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(mn2−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(m3.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.

Reviews

Required fields are marked *. Your email address will not be published.