Rounding of polytopes in the real number model of computation

• 成果类型: Article
• 署名作者: Khachiyan, LG
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.21.2.307
• 发表日期: 1996
• 页码: 307-320
• 关键词: ellipsoid method; variables

摘要

Let A be a set of m points in R(n). We show that the problem of (1 + epsilon)n-rounding of A,, i.e., the problem of computing an ellipsoid E subset of or equal to R(n) such that [(1 + epsilon)n](-1)E subset of or equal to conv. hull(A) subset of or equal to E, can be solved in O(mn(2)(epsilon(-1) + In n + In In m)) arithmetic operations and comparisons. This result implies that the problem of approximating the minimum volume ellipsoid circumscribed about A can be solved in O(m(3.5) In(m epsilon(-1))) operations to a relative accuracy of epsilon in the volume. The latter bound also applies to the (1 + epsilon)n-rounding problem. Our bounds hold for the real number model of computation.