[2311.09460] Near-Optimal Streaming Ellipsoidal Rounding for General Convex Poly...
source link: https://arxiv.org/abs/2311.09460
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Computer Science > Data Structures and Algorithms
Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes
We give near-optimal algorithms for computing an ellipsoidal rounding of a convex polytope whose vertices are given in a stream. The approximation factor is linear in the dimension (as in John's theorem) and only loses an excess logarithmic factor in the aspect ratio of the polytope. Our algorithms are nearly optimal in two senses: first, their runtimes nearly match those of the most efficient known algorithms for the offline version of the problem. Second, their approximation factors nearly match a lower bound we show against a natural class of geometric streaming algorithms. In contrast to existing works in the streaming setting that compute ellipsoidal roundings only for centrally symmetric convex polytopes, our algorithms apply to general convex polytopes. We also show how to use our algorithms to construct coresets from a stream of points that approximately preserve both the ellipsoidal rounding and the convex hull of the original set of points.
| Subjects: | Data Structures and Algorithms (cs.DS); Computational Geometry (cs.CG) |
| Cite as: | arXiv:2311.09460 [cs.DS] |
| (or arXiv:2311.09460v1 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2311.09460 |
Recommend
-
40
Multi-Period Trading via Convex Optimization considers a basic model of mult...
-
10
Determine if a point is located within a convex polygon It’s been a long time, but we are back again. We previously had discussed how to
-
10
Convex and Concave Dispositions Convex and Concave Dispositions 2020 Nov 08 See all posts Convex and Concave Dispositions One of the major philosophical differences that I have...
-
7
Important inequalities in convex optimization, proofs and intuition Many talk about data science and machine learning with enthusiasm, but few know about one of the most important building components behind them – con...
-
9
2021-05-11 02:15 Convex Finance将向veCRV用户空投CVX代币 Convex Finance今日公布了更多有关空投的细节，CVX代币将被空投到在快照区块期间持有veCRV的地址，以及投票赞成将Convex Finance列入Curve的白名单...
-
5
XBE Finance amplifies yield on $12bn Curve and Convex Liquidity – CryptoMode Search Curve.fi and Convex finance have fundamentally changed the way Decentralised Finance yield mec...
-
7
VisuAlgo - CONVEX_HULL_SUBTITLES slowfast slide 1 (20%) The Convex Hull of a set of points P is the smallest convex polygon CH(P) for which each point in P is either on the boundary of CH(P) or in i...
-
0
The order of vertices on a convex polygon 0 ...
-
4
Two-dimensional convex hulls in SAS Given a cloud of points in the plane, it can be useful to identify the convex hull of the points. The convex hull is the smallest convex set that contains the observations. For a finite set of poin...
-
2
Computer Science > Data Structures and Algorithms [Submitted on 20 Dec 2023] O(loglogn) Passes is Optimal for Semi-Streaming Ma...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK