1 citations · 1 across the 8 of their papers we have counts for
5 papers · 1 filter
Stronger Hardness for Submodular Maximization Subject to a Matroid Constraint
Moran Feldman, Alan Kuhnle
Maximizing a submodular function subject to a matroid constraint is a cornerstone problem in combinatorial optimization. The state-of-the-art algorithm for this problem obtains $0.…
Dynamic Contention Resolution Schemes
Moran Feldman, Gregory Kehne, Roie Levin +1
We introduce a low-recourse rounding paradigm for packing problems in fully dynamic settings, which we name Dynamic Contention Resolution Schemes (DCRSs). These are dynamic analogs…
On Maximizing a Weakly Submodular Function over a Matroid Constraint via the Greedy Algorithm
Justin Ward, Moran Feldman
We consider the problem of approximately maximizing a weakly submodular function using the standard greedy algorithm, which is known to give tight approximation results for such fu…
Semi-Streaming Algorithms for Submodular Maximization under Random Arrival Order
Niv Buchbinder, Moran Feldman, Siyue Liu +1
We study random order semi-streaming algorithms for submodular maximization under a wide range of combinatorial constraint classes, including matroids, matroid -parity, -exch…
Submodular Maximization over a Matroid -Intersection: Multiplicative Improvement over Greedy
Moran Feldman, Justin Ward
We study the problem of maximizing a non-negative monotone submodular objective subject to the intersection of arbitrary matroid constraints. The natural greedy algorithm g…