{"ID":23475954,"CreatedAt":"2026-09-18T01:09:05.407443952Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.19528","arxiv_id":"2609.19528","title":"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_{\\geq 0}$ in a certain class, we have $$\\max_{S \\in F} f(S) \\geq c(n) \\cdot \\max_{S \\subset [n]} f(S).$$ We prove that there is a family of subpolynomial size such that for any nonnegative submodular function, $c(n) = Ω(\\frac{\\log \\log n}{\\log n})$, and there is a family of logarithmic size such that $c(n) = Ω(\\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) \\geq \\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}})$.","short_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_{\\geq 0}$ in a certain class, we have $$\\max_{S \\in F} f(S) \\geq c(n) \\cdot \\max_{S \\subset [n]} f(S).$$ We prove that there is a family of subpolynomial size such that for any nonnegative su...","url_abs":"https://arxiv.org/abs/2609.19528","url_pdf":"https://arxiv.org/pdf/2609.19528v1","authors":"[\"Chandra Chekuri\",\"Richard Ueltzen\",\"Jan Vondrak\"]","published":"2026-09-17T00:46:15Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}