63 citations · 181 across the 15 of their papers we have counts for
16 papers
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…
Two-Sided Weak Submodularity for Matroid Constrained Optimization and Regression
Theophile Thiery, Justin Ward
We study the following problem: Given a variable of interest, we would like to find a best linear predictor for it by choosing a subset of relevant variables obeying a matroid…
FPT-Algorithms for the \ell-Matchoid Problem with a Coverage Objective
Chien-Chung Huang, Justin Ward
We consider the problem of optimizing a coverage function under a -matchoid of rank . We design fixed-parameter algorithms as well as streaming algorithms to compute an ex…
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(…
Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms
Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson +1
Clustering is a classic topic in optimization with -means being one of the most fundamental such problems. In the absence of any restrictions on the input, the best known algori…
A bi-criteria approximation algorithm for Means
Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko +1
We consider the classical -means clustering problem in the setting bi-criteria approximation, in which an algoithm is allowed to output clusters, and must produce a clu…
A New Framework for Distributed Submodular Maximization
Rafael da Ponte Barbosa, Alina Ene, Huy L. Nguyen +1
A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization prob…
The Power of Randomization: Distributed Submodular Maximization on Massive Datasets
Rafael da Ponte Barbosa, Alina Ene, Huy L. Nguyen +1
A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization prob…
Maximizing k-Submodular Functions and Beyond
Justin Ward, Stanislav Zivny
We consider the maximization problem in the value oracle model of functions defined on -tuples of sets that are submodular in every orthant and -wise monotone, where $k\geq 2…
Optimal approximation for submodular and supermodular optimization with bounded curvature
Maxim Sviridenko, Jan Vondrák, Justin Ward
We design new approximation algorithms for the problems of optimizing submodular and supermodular functions subject to a single matroid constraint. Specifically, we consider the ca…
Submodular Stochastic Probing on Matroids
Marek Adamczyk, Maxim Sviridenko, Justin Ward
In a stochastic probing problem we are given a universe , where each element is active independently with probability , and only a probe of e can tell us whether…
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…
A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint
Yuval Filmus, Justin Ward
We present an optimal, combinatorial 1-1/e approximation algorithm for monotone submodular optimization over a matroid constraint. Compared to the continuous greedy algorithm (Cali…
A -approximation algorithm for monotone submodular maximization over a -exchange system
Justin Ward
We consider the problem of maximizing a monotone submodular function in a -exchange system. These systems, introduced by Feldman et al., generalize the matroid k-parity problem…