Subset preservation conjecture for multiple monotone submodular functions
Subset preservation conjecture for multiple monotone submodular functions
Let be a constant, let be monotone submodular functions on a ground set , and let have size with for every . For an integer satisfying , there should exist a set of size such that
Subset preservation conjecture. Under these hypotheses, such a set 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.