Subset preservation conjecture for multiple monotone submodular functions

Let l1l\geq 1 be a constant, let f1,,flf_1,\dots,f_l be monotone submodular functions on a ground set NN, and let SNS\subseteq N have size kk with fi(S)Vif_i(S)\geq V_i for every i[l]i\in[l]. For an integer mm satisfying smls\geq m\geq l, there should exist a set XSX\subseteq S of size mm such that

fi(X)mΘ(1)kVi,i[l].f_i(X)\geq \frac{m-\Theta(1)}{k}V_i,\quad \forall i\in[l].

Subset preservation conjecture. Under these hypotheses, such a set XX exists. The claim would provide a simultaneous value guarantee for a constant number of monotone submodular objectives when reducing the cardinality of a feasible set; whether this general statement holds remains open.

Sources & referencesView supporting material

Primary source

James B. Orlin, Andreas S. Schulz and Rajan Udwani, “Robust Monotone Submodular Function Maximization”, arXiv:1507.06616 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.