Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes

Autor:	Makarychev, Yury, Manoj, Naren Sarayu, Ovsiankin, Max
Rok vydání:	2022
Předmět:	Computer Science - Data Structures and Algorithms Computer Science - Computational Geometry
Druh dokumentu:	Working Paper
Popis:	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. Comment: Accepted to COLT 2022
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2206.07250 Zobrazit plný text záznamu View this record from Arxiv