JW
Justin Ward
cs.DScs.DMcs.LGcs.AIcs.DCmath.OC
On Valency
published · living versionsW_455wf7yh·v1 · currentpublished
Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms
with Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson
1 version
Preprints & journals
16 papers in the corpus · 2011–2026On Maximizing a Weakly Submodular Function over a Matroid Constraint via the Greedy Algorithm2609.05008v1 · Justin Ward, Moran Feldman2026 · 0 citationsarXiv
Submodular Maximization over a Matroid $k$-Intersection: Multiplicative Improvement over Greedy2602.08473v3 · Moran Feldman, Justin Ward2026 · 0 citationsarXiv
Two-Sided Weak Submodularity for Matroid Constrained Optimization and Regression2102.09644v2 · Theophile Thiery, Justin Ward2021 · 0 citationsarXiv
An Improved Approximation for Maximum Weighted $k$-Set Packing2301.07537v1 · Theophile Thiery, Justin Ward2023 · 20 citationsarXiv
FPT-Algorithms for the \ell-Matchoid Problem with a Coverage Objective2011.06268v3 · Chien-Chung Huang, Justin Ward2020 · 2 citationsarXiv
Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints2102.09679v1 · Chien-Chung Huang, Theophile Thiery, Justin Ward2021 · 5 citationsarXiv
Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications1904.09354v1 · Christopher Harshaw, Moran Feldman, Justin Ward et al.2019 · 63 citationsarXiv
Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms1612.07925v2 · Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson et al.2016 · 119 citationsarXivon Valency
A New Framework for Distributed Submodular Maximization1507.03719v2 · Rafael da Ponte Barbosa, Alina Ene, Huy L. Nguyen et al.2015 · 67 citationsarXiv
Maximizing k-Submodular Functions and Beyond1409.1399v2 · Justin Ward, Stanislav Zivny2014 · 63 citationsACM Transactions on Algorithms 12(4) Article no. 47 (2016)
A bi-criteria approximation algorithm for $k$ Means1507.04227v2 · Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko et al.2015 · 27 citationsarXivon Valency
Optimal approximation for submodular and supermodular optimization with bounded curvature1311.4728v3 · Maxim Sviridenko, Jan Vondr'ak, Justin Ward2013 · 188 citationsarXiv
Submodular Stochastic Probing on Matroids1310.4415v4 · Marek Adamczyk, Maxim Sviridenko, Justin Ward2013 · 47 citationsarXiv
A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint1204.4526v4 · Yuval Filmus, Justin Ward2012 · 21 citationsarXiv
Large Neighborhood Local Search for the Maximum Set Packing Problem1302.4347v1 · Maxim Sviridenko, Justin Ward2013 · 29 citationsarXiv
A $(k + 3)/2$-approximation algorithm for monotone submodular maximization over a $k$-exchange system1108.4983v2 · Justin Ward2011 · 26 citations29th Symp. on Theoretical Aspects of Comp. Sci. (STACS 2012) 42-53
Career total: 45 works. 16 are in this corpus.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.