← 研踪 PaperTrailarXiv:2611.23637 · v1
Optimal universal sets for submodular functions
首次提交 2026-11-18 08:00
版本更新 2026-11-18 08:00
雷达观测 2026-11-19 19:08
摘要
We resolve the question of deterministic non-adaptive algorithms for nonnegative submodular maximization: We prove that for every and , there is a polynomial-size family , , such that for every nonnegative submodular function , . It is also easy to show that a factor better than cannot be achieved by any fixed polynomial-size family. A related result that we prove is that there is a distribution supported on polynomially many subsets of such that , where is the uniform distribution on , and 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 and taking the empirical mean does not converge to the true expectation uniformly for all submodular functions. The construction of and 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
观测到的版本
相邻记录可能跳过中间版本;首次发现 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 and , there is a polynomial-size family , , such that for every nonnegative submodular function , . It is also easy to show that a factor better than cannot be achieved by any fixed polynomial-size family. A related result that we prove is that there is a distribution supported on polynomially many subsets of such that , where is the uniform distribution on , and 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 and taking the empirical mean does not converge to the true expectation uniformly for all submodular functions. The construction of and 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.
查看此版本解读 →查看此版本原文 ↗