Universal set families for maximization of nonnegative submodular and XOS functions

Abstract

We consider the question of designing a universal family of sets $F\subset 2^{[n]}$ such that for any function $f:2^{[n]}\to R_{\ge 0}$ in a certain class, we have $$\underset{S\in F}{\max }f(S)\ge c(n)\cdot \underset{S\subset [n]}{\max }f(S).$$ We prove that there is a family of subpolynomial size such that for any nonnegative submodular function, $c(n)=\Omega (\frac{\log \log n}{\log n})$, and there is a family of logarithmic size such that $c(n)=\Omega (\frac{1}{\log n})$. We also prove that pairwise independence (which achieves a constant factor for graph cut functions), or even $k$-wise independence, does not imply a bound better than $O(\frac{1}{\sqrt{\log n}})$ for submodular functions. On the other hand, we prove that for any polynomially representable subclass of nonnegative submodular functions (such as the matroid connectivity functions for matroid representable over $F_q$), a constant-factor universal family of polynomial size always exists. For absolute XOS functions (a class that we introduce, in the form $f(S)={\max }_i|{\sum }_{j\in S}{w}_{ij}+c_i|$ where $w_{ij},c_i\in R$), we design a family of polynomial size such that $c(n)\ge \sqrt{\frac{\log n}{n}}$, and prove that there is no polynomial-size family achieving a factor better than $O(\sqrt{\frac{\log n}{n}})$.

The main results were obtained with ChatGPT-5.6 Sol