论文标题
凸多属的椭圆形近似的流算法
Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes
论文作者
论文摘要
我们提供有效的确定性一通流媒体算法，以找到对称凸层的椭圆形近似。该算法几乎是最佳的，因为它们的近似因子与最佳离线解决方案的近似因子仅通过因子亚属性在多层的纵横比中。
We give efficient deterministic one-pass streaming algorithms for finding an ellipsoidal approximation of a symmetric convex polytope. The algorithms are near-optimal in that their approximation factors differ from that of the optimal offline solution only by a factor sub-logarithmic in the aspect ratio of the polytope.
