48 citations · 62 across the 5 of their papers we have counts for
5 papers · 1 filter
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…
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…
Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints
Chien-Chung Huang, Theophile Thiery, Justin Ward
We give improved multi-pass streaming algorithms for the problem of maximizing a monotone or arbitrary non-negative submodular function subject to a general -matchoid constraint…
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(…
Large Neighborhood Local Search for the Maximum Set Packing Problem
Maxim Sviridenko, Justin Ward
In this paper we consider the classical maximum set packing problem where set cardinality is upper bounded by . We show how to design a variant of a polynomial-time local search…