← 研踪 PaperTrailarXiv:2606.20777 · v3
Nearly Optimal Submodular Sparsification, with and without Cardinality Constraints
首次提交 2026-06-19 00:16
版本更新 2026-11-03 20:18
雷达观测 2026-11-04 23:39
摘要
We study the sparsification of decomposable submodular functions: given a sum $F(S) = \sum_{i=1}^m f_i(S)$ of $m$ nonnegative submodular functions on an $n$-element ground set $[n]$ (without assuming monotonicity or symmetry), the goal is to find a sparse reweighting $\widetilde{F}(S) = \sum_{i=1}^m w_i f_i(S)$ with at most $s \ll m$ nonzero weights that preserves $F(S)$ within a $(1 \pm \varepsilon)$ factor across a target family of queries. For all subset queries $S \subseteq [n]$, we give a polynomial-time randomized algorithm that constructs a sparsifier of size $O(n^2 \log n / \varepsilon^2)$. This improves upon the previous best upper bound of $O(n^3 / \varepsilon^2)$ by Kenneth and Krauthgamer and resolves their open conjecture up to a logarithmic factor, matching the $Ω(n^2)$ lower bound from directed cuts. Motivated by capacity budgets in submodular applications and the Restricted Isometry Property (RIP) in compressed sensing, we further study submodular sparsification under a cardinality constraint $|S| \le k$, and obtain a polynomial-time algorithm that constructs a sparsifier of size $O(n k \log n / \varepsilon^2)$, nearly matching the $Ω(nk)$ lower bound. This shows that a cardinality constraint unconditionally reduces the size of general submodular sparsifiers by a factor of roughly $k/n$; we complement this with $Ω(n)$ lower bounds showing that even regular symmetric or almost-regular monotone submodular functions cannot be sparsified to $o(n)$ size for $k = 2$ and $k = 1$, respectively.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v3 · 2026-11-03 20:18 · 最新观测版本
Nearly Optimal Submodular Sparsification, with and without Cardinality Constraints
We study the sparsification of decomposable submodular functions: given a sum $F(S) = \sum_{i=1}^m f_i(S)$ of $m$ nonnegative submodular functions on an $n$-element ground set $[n]$ (without assuming monotonicity or symmetry), the goal is to find a sparse reweighting $\widetilde{F}(S) = \sum_{i=1}^m w_i f_i(S)$ with at most $s \ll m$ nonzero weights that preserves $F(S)$ within a $(1 \pm \varepsilon)$ factor across a target family of queries. For all subset queries $S \subseteq [n]$, we give a polynomial-time randomized algorithm that constructs a sparsifier of size $O(n^2 \log n / \varepsilon^2)$. This improves upon the previous best upper bound of $O(n^3 / \varepsilon^2)$ by Kenneth and Krauthgamer and resolves their open conjecture up to a logarithmic factor, matching the $Ω(n^2)$ lower bound from directed cuts. Motivated by capacity budgets in submodular applications and the Restricted Isometry Property (RIP) in compressed sensing, we further study submodular sparsification under a cardinality constraint $|S| \le k$, and obtain a polynomial-time algorithm that constructs a sparsifier of size $O(n k \log n / \varepsilon^2)$, nearly matching the $Ω(nk)$ lower bound. This shows that a cardinality constraint unconditionally reduces the size of general submodular sparsifiers by a factor of roughly $k/n$; we complement this with $Ω(n)$ lower bounds showing that even regular symmetric or almost-regular monotone submodular functions cannot be sparsified to $o(n)$ size for $k = 2$ and $k = 1$, respectively.
查看此版本解读 →查看此版本原文 ↗