Showing 2020Show all
2 papers · 1 filter
cs.DS2020
Fully-Dynamic Submodular Cover with Bounded Recourse
Anupam Gupta, Roie Levin
In submodular covering problems, we are given a monotone, nonnegative submodular function and wish to find the min-cost set such tha…
cs.DS2020
Streaming Submodular Matching Meets the Primal-Dual Method
Roie Levin, David Wajc
We study streaming submodular maximization subject to matching/-matching constraints (MSM/MSbM), and present improved upper and lower bounds for these problems. On the upper bou…