The thesis provides near-optimal streaming ellipsoidal rounding algorithms, block Lewis weight sparsification, dueling optimization with monotone adversaries, PAC analysis of backdoors, and spectral clustering robustness, all with detailed proofs.
Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
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.
fields
math.OC 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
A Geometric Approach to Problems in Optimization and Data Science
The thesis provides near-optimal streaming ellipsoidal rounding algorithms, block Lewis weight sparsification, dueling optimization with monotone adversaries, PAC analysis of backdoors, and spectral clustering robustness, all with detailed proofs.