1 citations · 1 across the 8 of their papers we have counts for
9 papers
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…
Bicriteria Submodular Maximization
Moran Feldman, Alan Kuhnle
Submodular functions and their optimization have found applications in diverse settings ranging from machine learning and data mining to game theory and economics. In this work, we…
Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization
Niv Buchbinder, Moran Feldman
Maximization of submodular functions under various constraints is a fundamental problem that has been studied extensively. A powerful technique that has emerged and has been shown…
Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint
Niv Buchbinder, Moran Feldman
We study the problem of maximizing a monotone submodular function subject to a matroid constraint, and present for it a deterministic non-oblivious local search algorithm that has…
Practical -Approximation for Submodular Maximization Subject to a Cardinality Constraint
Murad Tukan, Loay Mualem, Moran Feldman
Non-monotone constrained submodular maximization plays a crucial role in various machine learning applications. However, existing algorithms often struggle with a trade-off between…