CS Paper Radar

Optimal universal sets for submodular functions

Marek Adamczyk, Richard Ueltzen, Jan Vondrak

cs.DS ·submitted 2026-11-18 00:00 UTC · v1
theory

Abstract

We resolve the question of deterministic non-adaptive algorithms for nonnegative submodular maximization: We prove that for every $n \geq 2$ and $ε\in (0,\frac{1}{4})$, there is a polynomial-size family ${F}_{n,ε}$, $|{F}_{n,ε}| = n^{O(1/ε^2 \log (1/ε))}$, such that for every nonnegative submodular function $f:2^{[n]} \to {\bf R}$, $\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/4$ cannot be achieved by any fixed polynomial-size family. A related result that we prove is that there is a distribution ${D}_{n,ε}$ supported on polynomially many subsets of $[n]$ such that $(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 ${U}_n$ is the uniform distribution on $2^{[n]}$, and $f$ 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 ${U}_n$ and taking the empirical mean does not converge to the true expectation uniformly for all submodular functions. The construction of ${F}_{n,ε}$ and ${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.

Comment
Results obtained with the assistance of GPT-6 Astra

Closest papers

Nearest neighbours by meaning across the whole index.

Universal set families for maximization of nonnegative submodular and XOS functions

cs.DS ·2026-09-17 ·Chandra Chekuri, Richard Ueltzen, Jan Vondrak
theoryhot direction similarity 0.81
Abstract · The main results were obtained with ChatGPT-5.6 Sol

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}})$.

0.33

Improved Quasi-Polynomial-Time Approximation for Maximum Independent Set

cs.DS cs.CC ·2026-10-26 ·Zhao Song
similarity 0.65
Abstract

We give a deterministic quasi-polynomial-time algorithm for the maximum independent set problem. If an $N$-vertex graph contains an independent set of size $2^{-t}N$, where $t$ is an integer with $1\le t\le\sqrt{\log N}/12$, then our algorithm finds an independent set of size $2^t$ in time $N^{O(t)}$. This gives an approximation ratio of $N/2^{Ω(\sqrt{\log N})}$ in time $N^{O(\sqrt{\log N})}$, improving on the approximation ratio $N/2^{Ω((\log N)^{1/3})}$ obtained by Lovett [Lov26]. A limitation of this form of analysis follows from the integrality gaps of Tulsiani [Tul09]. These gaps imply that a universal guarantee of the form $\operatorname{Las}_{R(t)}(G)\ge2^{-t}N\Longrightarrowα(G)\ge2^t$, at $2^{o(\sqrt{\log N\log\log N})}$ levels, cannot hold over a range extending beyond $t=O(\sqrt{\log N\log\log N})$. Thus, the exponent $1/2$ is the limit of this form of analysis, up to a factor of $\sqrt{\log\log N}$.

0.23

Tight Bounds for Non-Monotone Submodular Maximization under a Cardinality Constraint with Constant Recourse

cs.DS cs.LG ·2026-11-15 ·Vaneet Aggarwal
theory similarity 0.64
Abstract

We study the maximization of a nonnegative submodular function under a cardinality constraint when elements arrive one at a time and an algorithm must report a feasible set after every arrival. The recourse of an algorithm is the largest number of insertions and deletions that it makes to the reported set at a single arrival. For every $ε>0$, we give an algorithm with recourse $O(ε^{-2})$ whose reported set has, at every time, expected value at least $1/4-ε$ times the largest value of a feasible set of arrived elements. The algorithm evaluates the function polynomially often, and only on sets of arrived elements. We also show that no algorithm with constant recourse achieves a ratio above $1/4$, even if it knows the function and the arrival order in advance and has unlimited computation, and that any fixed ratio above $1/4$ requires recourse that grows as a positive power of the cardinality budget. Thus $1/4$ is the optimal limiting ratio with constant recourse. The previous best ratio with constant recourse was $3-2\sqrt2\approx0.172$. Our algorithm assigns selection probabilities of at most one half and maintains, as elements arrive, an inequality bounding the value of every feasible set by a multiple of the expected value of a random set drawn with these probabilities; the reported set moves to a rounding of these probabilities through gradual replacements. The upper bound uses a weighted directed graph whose vertices arrive in groups of decreasing sizes.

0.12

Bounded Relative Boundary Implies Narrow DNF Approximation

cs.CC cs.DM ·2026-08-31 ·Chenghua Liu, Boning Meng
theory similarity 0.64
Abstract · 13 pages; proof and exposition revised, Lean repository linked

We prove Friedgut's conjecture (J. Amer. Math. Soc. 12 (1999)) that every increasing family in the $p$-biased discrete cube with bounded relative boundary can be approximated arbitrarily well by one whose minimal elements have size bounded independently of the dimension and the bias. For $0<p\le 1/2$, every increasing Boolean function with total resampling influence at most $K$ is $\varepsilon$-close under $μ_p^n$ to a monotone DNF of width $\exp(O((K+1)^2/\varepsilon^2))$, from which the full conjecture follows for all $p\in(0,1)$. We build on Hatami's pseudo-junta theorem (Ann. of Math. 176 (2012)), whose approximator need not be increasing. Our randomized shifts produce an increasing approximator that is measurable with respect to a controlled refinement of Hatami's adaptive partition. Retaining only short positive certificates yields the desired narrow DNF.

0.35

Optimal Polynomial-Query Approximation for Consistent Submodular Maximization with Short Lookahead

cs.DS cs.LGmath.OC ·2026-11-08 ·Vaneet Aggarwal
similarity 0.63
Abstract

Elements arrive one at a time, and after each arrival an algorithm holds a set of at most $k$ arrived elements. Its goal is a held set whose value under a monotone submodular function is close to the best value that $k$ arrived elements can achieve. The recourse of an update is the number of elements inserted into or removed from the held set, and we require it to be bounded independently of $k$ and of the number $n$ of arrivals. With evaluations only on sets of arrived elements and polynomially many of them, the best ratio a randomized algorithm can achieve is $2-\sqrt{2}\approx0.5858$. We show that seeing future arrivals raises the best ratio for polynomially many evaluations to $1-1/e\approx0.6321$, for deterministic and for randomized algorithms; no algorithm with polynomially many evaluations exceeds $1-1/e$, even when all elements are available at once. For every $\varepsilon>0$, a deterministic algorithm that sees the next $\lceil\varepsilon k/3\rceil$ arrivals keeps a set of value at least $1-1/e-\varepsilon$ times the optimum at every time, changes $O(\varepsilon^{-3})$ elements per arrival and makes $(n+1)^{O(\varepsilon^{-2})}$ evaluations. With the whole arrival sequence known in advance, a deterministic algorithm attains the same ratio with $O(\varepsilon^{-2})$ changes per arrival. A randomized algorithm with the same short lookahead makes $O(n^2k)$ evaluations, changes $O(\varepsilon^{-2})$ elements per arrival, and attains the same ratio in expectation at each fixed time. The main tool is a greedy algorithm with an explicit guarantee for each of its partial solutions combined with each initial segment of the known future arrivals. A second tool moves between two such solutions one element at a time while keeping the value high, and the deterministic algorithm times each move using upper bounds on the optimum from failed searches.

0.16

From Linear to Polylogarithmic: Dynamic Submodular Maximization over Matroids

cs.DS ·2026-10-26 ·Kiarash Banihashem, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Morteza Monemizadeh
similarity 0.63
Abstract

We study the problem of submodular maximization under a matroid constraint. In this problem, there is a monotone submodular function $f: 2^{N} \rightarrow \mathbb{R}^+$ and a matroid $M(N, I)$, accessible via value and independence oracles and the goal is to find the independent set $S \in I$ maximizing the objective function, i.e., $f(S) = \max_{I \in I} f(I)$. In the fully dynamic setting, the active ground set $N \subseteq N$ evolves through element insertions and deletions. The goal is to maintain a solution $S \subseteq N$ with $S \in I$ and $f(S) = \max_{I \subseteq N,, I \in I} f(I)$ after each update. Two approximation algorithms have been proposed to solve this problem: Dütting et al. developed a $(4+ε)$-approximation algorithm with an expected amortized update time of $O\!\bigl(\frac{k^2}ε \log k \log n \log^3 \frac{k}ε\bigr)$, and Banihashem et al. achieved a similar approximation with a better update time $O\!\bigl(k \log k \log^3 \frac{k}ε\bigr)$. However, these methods both become inefficient when the rank $k$ of the matroid is large (e.g., when $k = n^{o(1)}$). The central open question in this line of work is whether a fully dynamic algorithm with polylogarithmic update time exists. We resolve this question by presenting the first fully dynamic algorithm for submodular maximization over matroids with polylogarithmic update time. Our algorithm maintains a $(4+ε)$-approximate solution with expected amortized update time $poly(\log n, ε^{-1})$, where $n = |N|$. In particular, the update time is independent of the matroid rank $k$, thereby eliminating the dependence on $k$ and settling the open problem.

0.30

A Sharp Barrier of Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse

cs.DS cs.LG ·2026-09-09 ·Shi Fu, Qixin Zhang, Dacheng Tao
theory similarity 0.62
Abstract

Consistent submodular maximization aims to maintain a high-utility subset of size at most $k$ as new elements arrive one by one, while changing only a limited number of elements per update. Previously, [DFL+25](STOC '25) established an information-theoretic bound of $2/3$ and gave the first polynomial-time randomized algorithm with a $0.51$-approximation guarantee. However, a fundamental question remained open: Is it possible to design an efficient algorithm for consistent submodular maximization that matches the classical offline $(1-1/e)$-approximation? In this paper, we answer this question in the negative by proving that the sharp approximation threshold achievable with polynomially many value queries and worst-case constant recourse is \[β:=2-\sqrt{2}\approx0.5858<1-1/e.\] Specifically, we develop an improved poly-time randomized algorithm, which can attain a $(β-\varepsilon)$-approximation in expectation at each fixed time with $O(\varepsilon^{-2})$ worst-case recourse. The cornerstone of this algorithm is a novel anchored sampling scheme, which uses only value queries on subsets of the elements seen so far to construct a solution that remains competitive under unknown future arrivals. Conversely, we establish a matching lower bound by showing that any fixed improvement over $β$ requires either exponentially many value queries or $Ω(k)$ changes per update. Furthermore, we characterize the impact of curvature by establishing a sharp threshold of $1-(\sqrt{2}-1)\vartheta$ for consistent submodular maximization, where $\vartheta\in[0,1]$ denotes the total curvature. Surprisingly, for weighted coverage objectives, we devise a poly-time randomized algorithm that can match the optimal $(1-1/e-\varepsilon)$-approximation with $O(\varepsilon^{-1})$ worst-case recourse, thereby separating coverage maximization from general submodular maximization in the consistent settings.

0.45

Fully Dynamic Unconstrained Submodular Maximization

cs.DS ·2026-10-28 ·Mohammad Hajiaghayi
theory similarity 0.61
Abstract

We study unconstrained maximization of a fixed nonnegative submodular function when the ground set changes by insertions and deletions. A uniformly random subset gives a $1/4$-approximation with constantly many value-oracle queries per update. We obtain improvements over this bound for arbitrary oblivious update sequences, without knowing future deletions. For value estimation, we give a $(\sqrt2-1-\varepsilon)$-approximation using $O_{\varepsilon,δ}(\log^2(N+1))$ expected amortized oracle queries, with failure probability at most $δ$ at each fixed time. Here $N$ bounds the number of active elements. The algorithm maintains Poisson samples of the positive mass of random chain lower bounds. We prove that the factor $\sqrt2-1$ is tight for this certificate, even when polynomially many independent orders are used. For every fixed integer $K\ge2$, we maintain a feasible $(1/4+Ω(K^{-2}))$-approximate set using $\widetilde O_K(N^{1/K})$ amortized queries. Thus every fixed exponent $γ>0$ permits a fixed improvement over $1/4$ with $\widetilde O_γ(N^γ)$ update queries. In the square-root regime, a stronger algorithm attains $ρ_{\rm sq}-\varepsilon$, where $ρ_{\rm sq}>0.3177$. The maintained sets are feasible after every update, and their approximation guarantees hold in expectation. All bounds count oracle queries; the value estimator may query previously seen inactive elements, whereas the set algorithms use only currently active elements.

0.07