5 problems

Given a sequence of insertions of elements into a ground set, a monotone submodular function $f$ accessible through value queries, and a cardinality bound $k$, does there exist a r…

For every integer $n\ge 1$, every monotone submodular function $f:2^{[n]}\to\mathbb{R}_{\ge 0}$, and every marginal vector $x\in[0,1]^n$ with $f^{++}(x)>0$, the correlation gap und…

Let $S$ be the set of autonomous vehicles in the mixed traffic system, let $J_1(S)=-\lVert \mathbf{G}_1(S)\rVert_2^2$ be the negative squared $\mathcal{H}_2$ norm of the transfer f…

Submodular separation conjecture. For every such $r,d$, there exists a submodular function $f$ such that $f(x)$ is computable in $\mathrm{poly}(n)$ time, $f(x)\leqslant-1$ for ever…

Subset preservation conjecture. Under these hypotheses, such a set $X$ exists. The claim would provide a simultaneous value guarantee for a constant number of monotone submodular o…