Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes
Abstract
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.
Cite
Text
Makarychev et al. "Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes." Conference on Learning Theory, 2022.Markdown
[Makarychev et al. "Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes." Conference on Learning Theory, 2022.](https://mlanthology.org/colt/2022/makarychev2022colt-streaming/)BibTeX
@inproceedings{makarychev2022colt-streaming,
title = {{Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes}},
author = {Makarychev, Yury and Manoj, Naren Sarayu and Ovsiankin, Max},
booktitle = {Conference on Learning Theory},
year = {2022},
pages = {3070-3093},
volume = {178},
url = {https://mlanthology.org/colt/2022/makarychev2022colt-streaming/}
}