Rounding of polytopes in the real number model of computation
Rounding of polytopes in the real number model of computation
复制标题
DOI：
10.1287/moor.21.2.307
复制
发表时间：
1996-05-01
影响因子：
1.7
通讯作者：
Khachiyan, LG
中科院分区：
文献类型：
--
作者：
Khachiyan, LG
令A为R（n）中的一组M点。我们表明（1 + epsilon）n连接的问题是，计算椭圆形E子集或等于r（n）的问题，因此[（1 + epsilon）n]（ - 1） E子集或等于Conv。船体（a）子集的子集或等于e，可以在O（Mn（2）（epsilon（-1） + in m in m））中求解算术操作和比较。该结果意味着，可以在O（m epsilon（-1））操作的O（m（3.5））操作中求解近似于A的最小体积椭圆形的问题，以达到体积中Epsilon的相对精度。后者的结合也适用于（1 + epsilon）n连接问题。我们的界限适用于实际数量的计算模型。
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.