11 problems

Let $N$ be a ground set with $|N|=n$, let $f:2^N\to\mathbb{R}_+$ be a nonnegative monotone submodular function, and let $\boldsymbol{x}\in[0,1]^n$. Let $f^+(\boldsymbol{x})$ be the…

Let the objective functions be general submodular functions and let the feasible sets be subject to general matroid constraints in the bandit setting. Wan et al.'s impossibility co…

Let P1 denote the sensor-placement optimization problem defined in the paper, and let the logarithmic determinant objective function associated with P1 be viewed as a set function…

Let the objective function be submodular, let its curvature be the corresponding curvature parameter, and let $\ell$ denote the number of candidate solutions used by the algorithms…

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…

Iterative-refinement convergence conjecture. The observed convergence of the upper bound and of the cumulative moving average is due to the fact that Algorithm GBDP refines the val…

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…

Variation conjecture. There exists a set $S$ of size $k'$ such that

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…

Let $f_1,\dots,f_l$ be a fixed number of monotone submodular functions on a ground set $N$. Greedy generalization conjecture. The greedy algorithm can be generalized to work for mu…

Let $G$ be a connected graph, let $varphi$ be a submodular cost function, and let the $varphi$-MST denote a minimum spanning tree of $G$ under the cost function $varphi$. A random…