ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let l≥1l\geq 1 be a constant, let f1,…,flf_1,\dots,f_l be monotone submodular functions on a ground set NN, and let S⊆NS\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 s≥m≥ls\geq m\geq l, there should exist a set X⊆SX\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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.