Dr Justin Ward
Senior Lecturer in Optimisation
Lead for Research Innovation and External Stakeholders Engagement
School of Mathematical Sciences
Queen Mary University of London
Queen Mary University of London
Research
Theory of Computing, Design and Analysis of Algorithms, Discrete Optimisation
Interests
My research interests include theoretical computer science, in particular the development and analysis of algorithms. Specfically, my research concerns approximation algorithms, combinatorial optimisation, and optimisation of submodular functions. I am also interested in models of simple, combinatorial algorithms, such as local search and greedy algorithms, for general combinatorial optimisation problems.Publications
Publications of specific relevance to the Centre for Combinatorics, Algebra and Number Theory2023
FPT-Algorithms for the l-Matchoid Problem with a Coverage ObjectiveHuang C-C Ward J
Siam Journal on Discrete Mathematics, Society For Industrial and Applied Mathematics
15-06-2023
2022
Two-Sided Weak Submodularity for Matroid Constrained Optimization and RegressionThiery T Ward J
35th Annual Conference on Learning Theory. vol. 178, 3605-3634.
01-01-2022
2020
Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid ConstraintsHuang C-C Thiery T Ward J
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)., 62:1-62:19.
11-08-2020
2019
Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual AlgorithmsAhmadian S Norouzi-Fard A Svensson O Ward J
Siam Journal on Computing, Society For Industrial & Applied Mathematics (Siam) vol. 49 (4)
22-10-2019
2017
Better Guarantees for K-Means and Euclidean K-Median by Primal-Dual AlgorithmsAhmadian S Norouzi-Fard A Svensson O Ward J
2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)., 61-72.
01-10-2017
Optimal Approximation for Submodular and Supermodular Optimization with Bounded CurvatureSviridenko M Vondrák J Ward J
Mathematics of Operations Research
16-05-2017
2016
A New Framework for Distributed Submodular MaximizationDa Ponte Barbosa R Ene A Nguyên HL Ward J
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)., 645-654.
01-10-2016
Maximizing k-Submodular Functions and BeyondWard J Živný S
Acm Transactions on Algorithms, Association For Computing Machinery (Acm) vol. 12 (4), 1-26.
03-08-2016
Submodular Stochastic Probing on MatroidsAdamczyk M Sviridenko M Ward J
Mathematics of Operations Research, Institute For Operations Research and The Management Sciences (Informs) vol. 41 (3), 1022-1038.
01-08-2016
A Bi-Criteria Approximation Algorithm for k-MeansMakarychev K Makarychev Y Sviridenko M Ward J Jansen K Mathieu C Rolim JDP Umans C
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, September 7-9, 2016, Paris, France. vol. 60, 14:1-14:20.
01-01-2016
2015
The Power of Randomization: Distributed Submodular Maximization on Massive DatasetsBarbosa RDP Ene A Nguyen HL Ward J Bach FR Blei DM
International Conference on Machine Learning Research Lille, France 7 Jul 2015 - 9 Jul 2015. vol. 37, 1236-1244.
01-07-2015
2014
Optimal approximation for submodular and supermodular optimization with bounded curvatureSviridenko M Vondrák J Ward J
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms., 1134-1148.
22-12-2014
Monotone Submodular Maximization over a Matroid via Non-Oblivious Local SearchFilmus Y Ward J
Siam Journal on Computing, Society For Industrial & Applied Mathematics (Siam) vol. 43 (2), 514-542.
01-01-2014
Submodular Stochastic Probing on MatroidsAdamczyk M Sviridenko M Ward J Mayr EW Portier N
31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5-8, 2014, Lyon, France. vol. 25, 29-40.
01-01-2014
2013
Maximizing Bisubmodular and k -Submodular FunctionsWard J Živný S
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms., 1468-1481.
18-12-2013
Large Neighborhood Local Search for the Maximum Set Packing ProblemSviridenko M Ward J
Lecture Notes in Computer Science. vol. 7965, 792-803.
01-01-2013
2012
A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid ConstraintFilmus Y Ward J
2012 IEEE 53rd Annual Symposium on Foundations of Computer Science., 659-668.
01-10-2012
A (k+3)/2-approximation algorithm for monotone submodular k-set packing and general k-exchange systemsWard J Dürr C Wilke T
29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France. vol. 14, 42-53.
01-01-2012
The Power of Local Search: Maximum Coverage over a MatroidFilmus Y Ward J Dürr C Wilke T
29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France. vol. 14, 601-612.
01-01-2012
2011
Improved Approximations for k-Exchange SystemsFeldman M Naor JS Schwartz R Ward J
Lecture Notes in Computer Science. vol. 6942, 784-798.
01-01-2011
2005
PrufrockWard J Kimmell G Alexander P
Proceedings of the 20th IEEE/ACM International Conference on Automated Software Engineering., 423-426.
07-11-2005
Submodular Maximization over a Matroid k-Intersection: Multiplicative Improvement over GreedyFeldman M Ward J
International Colloquium on Automata, Languages, and Programming Royal Holloway, University of London 6 Jul 2026 - 10 Jul 2026.
Submodular Maximization beyond Non-negativity: Guarantees, Fast Algorithms, and ApplicationsHarshaw C Feldman M Ward J Karbasi A
Proceedings of the 36th International Conference on Machine Learning (ICML '19) Long Beach, CA, USA. vol. 97, 2634-2643.
An Improved Approximation for Maximum Weighted k-Set PackingThiery T Ward J
ACM-SIAM Symposium on Discrete Algorithms Florence, Italy.
Grants
Grants of specific relevance to the Centre for Combinatorics, Algebra and Number TheoryEPSRC New Investigator Award - Dr Justin WardJustin Ward
£121,643 EPSRC Engineering and Physical Sciences Research Council
01-09-2019 - 31-08-2022
Research Group
News
No news items found.