Metraipolis › archive › dc_bb5f9d2766ff
Optimal Sparsifiers for Minkowski Sums and Sums of Seminorms — arXiv:2609.20238
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.20238
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-10T05:39:45.806Z
- SHA-256 of the archived text
a2fc706886782ec2dfc021f699e2adf54c5e5df8fd870367641b1336441effb7- Stable URL of this page
https://metraipolis.com/documento/dc_bb5f9d2766ff
How to cite
Optimal Sparsifiers for Minkowski Sums and Sums of Seminorms — arXiv:2609.20238 — arXiv (en), https://arxiv.org/abs/2609.20238 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bb5f9d2766ff (Metraipolis archive dc_bb5f9d2766ff, sha256 a2fc706886782ec2dfc021f699e2adf54c5e5df8fd870367641b1336441effb7)
BibTeX
@misc{dcbb5f9d2766ff,
title = {Optimal Sparsifiers for Minkowski Sums and Sums of Seminorms — arXiv:2609.20238},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.20238},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bb5f9d2766ff; sha256 a2fc706886782ec2dfc021f699e2adf54c5e5df8fd870367641b1336441effb7},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.20238. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We extend the recent work of Reis and Rothvoss on sparsifying sums of $\ell_1$ norms to the more general task of sparsifying (Minkowski) sums of centrally symmetric, convex sets. As our main result, we prove that for any $\varepsilon > 0$ and centrally symmetric, convex sets $C_1, \ldots, C_m\subseteq\mathbb{R}^n$ there is a choice of weights $\lambda_1, \dots , \lambda_m \in \mathbb{R}_{\geq 0}$ such that at most $O(n / \varepsilon^2)$ of the weights are non-zero, and \[(1 - \varepsilon)\cdot C\subseteq\sum_{i = 1}^m\lambda_i\cdot C_i\subseteq(1 + \varepsilon)\cdot C,\] where $C:= C_1 + \cdots + C_m$ refers to the Minkowski sums of the sets $C_1, \ldots, C_m$, and $\lambda\cdot C$ refers to the dilation of the set $C$. As immediate applications of this result, we obtain sparsifiers of size $O(n / \varepsilon^2)$ for sparsifying sums of seminorms in $n$-dimensional space, improving on the $O\left ( \frac{n \log(n/\varepsilon) \cdot \log^{2.5}(n)}{\varepsilon^2} \right )$ size sparsifiers from the work of Jambulapati, Lee, Liu, and Sidford (FOCS 2023). This further yields optimal size hypergraph cut sparsifiers with $O(n / \varepsilon^2)$ hyperedges, improving on the $O(n \log(n) / \varepsilon^2)$ size sparsifiers from the work of Chen, Khanna, and Nagda (FOCS 2020). More generally, this also gives optimal size sparsifiers for sums of symmetric submodular functions.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-18 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Metric Geometry (math.MG).
Pagina del lavoro: https://arxiv.org/abs/2609.20238 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T05:08:06.565Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).