48 citations · 282 across the 41 of their papers we have counts for
Showing 2019 · cs.DSShow all
3 papers · 2 filters
cs.DS2019★ 3 cited
Making a Sieve Random: Improved Semi-Streaming Algorithm for Submodular Maximization under a Cardinality Constraint
Naor Alaluf, Moran Feldman
In this paper we consider the problem of maximizing a non-negative submodular function subject to a cardinality constraint in the data stream model. Previously, the best known algo…
cs.DS2019
Almost Optimal Semi-streaming Maximization for k-Extendible Systems
Moran Feldman, Ran Haba
In this paper we consider the problem of finding a maximum weight set subject to a -extendible constraint in the data stream model. The only non-trivial algorithm known for this…
cs.DS2019★ 48 cited
Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications
Christopher Harshaw, Moran Feldman, Justin Ward +1
It is generally believed that submodular functions -- and the more general class of -weakly submodular functions -- may only be optimized under the non-negativity assumption $f(…