跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.23637 · v1

Optimal universal sets for submodular functions

首次提交 2026-11-18 08:00
版本更新 2026-11-18 08:00
雷达观测 2026-11-19 19:08
arXiv ↗PDF ↗

摘要

We resolve the question of deterministic non-adaptive algorithms for nonnegative submodular maximization: We prove that for every n≥2n \geq 2 and ε∈(0,14)ε\in (0,\frac{1}{4}), there is a polynomial-size family Fn,ε{F}_{n,ε}, ∣Fn,ε∣=nO(1/ε2log⁡(1/ε))|{F}_{n,ε}| = n^{O(1/ε^2 \log (1/ε))}, such that for every nonnegative submodular function f:2[n]→Rf:2^{[n]} \to {\bf R}, max⁡S∈Fn,εf(S)≥(1/4−ε)max⁡S⊆[n]f(S)\max_{S \in {F}_{n,ε}} f(S) \geq (1/4 - ε) \max_{S \subseteq [n]} f(S). It is also easy to show that a factor better than 1/41/4 cannot be achieved by any fixed polynomial-size family. A related result that we prove is that there is a distribution Dn,ε{D}_{n,ε} supported on polynomially many subsets of [n][n] such that (1−ε)ER∼Un[f(R)]≤ER∼Dn,ε[f(R)]≤ER∼Un[f(R)](1 - ε) {\bf E}_{R \sim {U}_n}[f(R)] \leq {\bf E}_{R \sim {D}_{n,ε}}[f(R)] \leq {\bf E}_{R \sim {U}_n}[f(R)], where Un{U}_n is the uniform distribution on 2[n]2^{[n]}, and ff is any nonnegative submodular function. This is interesting in light of the fact that uniform convergence does not hold for submodular functions: Sampling polynomially many sets from Un{U}_n and taking the empirical mean does not converge to the true expectation uniformly for all submodular functions. The construction of Fn,ε{F}_{n,ε} and Dn,ε{D}_{n,ε} is based on a new semidefinite extension of submodular functions: We show that the Goemans-Williamson rounding technique for a near-orthogonal arrangement of vectors gives a value close to the uniform expectation, and this rounding can be derandomized, since near-orthogonal vectors can be constructed in logarithmic dimension.

作者备注:Results obtained with the assistance of GPT-6 Astra

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-18 08:00 · 最新观测版本

Optimal universal sets for submodular functions

We resolve the question of deterministic non-adaptive algorithms for nonnegative submodular maximization: We prove that for every n≥2n \geq 2 and ε∈(0,14)ε\in (0,\frac{1}{4}), there is a polynomial-size family Fn,ε{F}_{n,ε}, ∣Fn,ε∣=nO(1/ε2log⁡(1/ε))|{F}_{n,ε}| = n^{O(1/ε^2 \log (1/ε))}, such that for every nonnegative submodular function f:2[n]→Rf:2^{[n]} \to {\bf R}, max⁡S∈Fn,εf(S)≥(1/4−ε)max⁡S⊆[n]f(S)\max_{S \in {F}_{n,ε}} f(S) \geq (1/4 - ε) \max_{S \subseteq [n]} f(S). It is also easy to show that a factor better than 1/41/4 cannot be achieved by any fixed polynomial-size family. A related result that we prove is that there is a distribution Dn,ε{D}_{n,ε} supported on polynomially many subsets of [n][n] such that (1−ε)ER∼Un[f(R)]≤ER∼Dn,ε[f(R)]≤ER∼Un[f(R)](1 - ε) {\bf E}_{R \sim {U}_n}[f(R)] \leq {\bf E}_{R \sim {D}_{n,ε}}[f(R)] \leq {\bf E}_{R \sim {U}_n}[f(R)], where Un{U}_n is the uniform distribution on 2[n]2^{[n]}, and ff is any nonnegative submodular function. This is interesting in light of the fact that uniform convergence does not hold for submodular functions: Sampling polynomially many sets from Un{U}_n and taking the empirical mean does not converge to the true expectation uniformly for all submodular functions. The construction of Fn,ε{F}_{n,ε} and Dn,ε{D}_{n,ε} is based on a new semidefinite extension of submodular functions: We show that the Goemans-Williamson rounding technique for a near-orthogonal arrangement of vectors gives a value close to the uniform expectation, and this rounding can be derandomized, since near-orthogonal vectors can be constructed in logarithmic dimension.

查看此版本解读 →查看此版本原文 ↗