Dr Justin Ward

Justin Ward

Senior Lecturer in Optimisation

School of Mathematical Sciences
Queen Mary University of London

Publications

solid heart iconPublications of specific relevance to the Centre for Combinatorics, Algebra and Number Theory

2023

bullet iconFPT-Algorithms for the l-Matchoid Problem with a Coverage Objective
Huang C-C and Ward J
Siam Journal on Discrete Mathematics, Society For Industrial and Applied Mathematics 
15-06-2023

2022

bullet iconTwo-Sided Weak Submodularity for Matroid Constrained Optimization and Regression
Thiery T and Ward J
35th Annual Conference on Learning Theory. vol. 178, 3605-3634. Editors: Po-Ling L and Raginsky M. 
01-01-2022

2020

bullet iconImproved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints
Huang C-C, Thiery T and Ward J
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)., 62:1-62:19. Editors: Byrka J and Meka R. 
11-08-2020

2019

bullet iconBetter Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms
Ahmadian S, Norouzi-Fard A, Svensson O and Ward J
Siam Journal on Computing, Society For Industrial and Applied Mathematics vol. 49 (4), 97-156.  
22-10-2019

2017

bullet iconBetter Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms
Ahmadian S, Norouzi-Fard A, Svensson O and Ward J
2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)., 61-72. Editors: Umans C. 
13-11-2017
bullet iconOptimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature
Sviridenko M, Vondrák J and Ward J
Mathematics of Operations Research 
16-05-2017

2016

bullet iconA New Framework for Distributed Submodular Maximization
Barbosa RDP, Ene A, Nguyen HL and Ward J
IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA., 645-654. Editors: Dinur I. 
01-01-2016
bullet iconA Bi-Criteria Approximation Algorithm for k-Means
Makarychev K, Makarychev Y, Sviridenko M and Ward J
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, September 7-9, 2016, Paris, France. vol. 60, 14:1-14:20. Editors: Jansen K, Mathieu C, Rolim JDP and Umans C. 
01-01-2016
bullet iconSubmodular Stochastic Probing on Matroids
Adamczyk M, Sviridenko M and Ward J
Math. Oper. Res. vol. 41, 1022-1038.  
01-01-2016
bullet iconMaximizing k-Submodular Functions and Beyond
Ward J and Zivny S
Acm Trans. Algorithms vol. 12, 47:1-47:26.  
01-01-2016

2015

bullet iconThe Power of Randomization: Distributed Submodular Maximization on Massive Datasets
Barbosa RDP, Ene A, Nguyen HL and Ward J
International Conference on Machine Learning Research Lille, France 7 Jul 2015 - 9 Jul 2015. vol. 37, 1236-1244. Editors: Bach FR and Blei DM. 
01-07-2015
bullet iconOptimal approximation for submodular and supermodular optimization with bounded curvature
Sviridenko M, Vondrák J and Ward J
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015., 1134-1148. Editors: Indyk P. 
01-01-2015

2014

bullet iconMonotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
Filmus Y and Ward J
Siam J. Comput. vol. 43, 514-542.  
01-01-2014
bullet iconMaximizing Bisubmodular and k-Submodular Functions
Ward J and Zivny S
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014., 1468-1481. Editors: Chekuri C. 
01-01-2014
bullet iconSubmodular Stochastic Probing on Matroids
Adamczyk M, Sviridenko M and Ward J
31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5-8, 2014, Lyon, France. vol. 25, 29-40. Editors: Mayr EW and Portier N. 
01-01-2014

2013

bullet iconLarge Neighborhood Local Search for the Maximum Set Packing Problem
Sviridenko M and Ward J
Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I. vol. 7965, 792-803. Editors: Fomin FV, Freivalds R, Kwiatkowska MZ and Peleg D. 
01-01-2013

2012

bullet iconA Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint
Filmus Y and Ward J
53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012., 659-668.  
01-01-2012
bullet iconA (k+3)/2-approximation algorithm for monotone submodular k-set packing and general k-exchange systems
Ward J
29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France. vol. 14, 42-53. Editors: Dürr C and Wilke T. 
01-01-2012
bullet iconThe Power of Local Search: Maximum Coverage over a Matroid
Filmus Y and Ward J
29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France. vol. 14, 601-612. Editors: Dürr C and Wilke T. 
01-01-2012

2011

bullet iconImproved Approximations for k-Exchange Systems - (Extended Abstract)
Feldman M, Naor J, Schwartz R and Ward J
Algorithms - ESA 2011 - 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011. Proceedings. vol. 6942, 784-798. Editors: Demetrescu C and Halldórsson MM. 
01-01-2011

2005

bullet iconPrufrock: a framework for constructing polytypic theorem provers
Ward J, Kimmell G and Alexander P
20th IEEE/ACM International Conference on Automated Software Engineering (ASE 2005), November 7-11, 2005, Long Beach, CA, USA., 423-426. Editors: Redmiles DF, Ellman T and Zisman A. 
01-01-2005