Justin Ward
I am a Lecturer in the
School of Mathematical Sciences
at Queen Mary University of London. I specialise in Optimisation and Operations Research.
Research
|
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.
|
Bio
|
I completed my PhD at the University of Toronto under the supervision of
Allan Borodin. From 2012 to 2015, I was a Research Fellow in the
Department of Computer Science and
Centre for Discrete Mathematics and its Applications at the
University of Warwick. From 2015 until 2017, I was a Research Scientist in the Theory of Computation Laboratory at EPFL.
|
Contact Information
E-mail |
firstname dot lastname at qmul dot ac dot uk
|
Phone |
+44 20 7882 5065 |
Office |
MB-126 Mathematical Sciences Building
|
Office Hours |
Wednesdays 10:00-12:00
and other times by appointment
|
Address |
School of Mathematical Sciences
327 Mile End Road
Queen Mary University of London
London E1 4NS
|
Teaching and Service
Current Teaching (Fall 2023)
I am currently teaching the following modules. See the linked QMPlus page for all module-related information.
- MTH785P: Programming for Business Analytics
Previous Teaching
- MTH785P Programming for Business Analytics (Spring 2018--2022)
- MTH5114 Linear Programming and Games (Spring 2018--2022)
- MTH6109 Combinatorics (Fall 2017)
Workshops and Conferences
I have recently served on the program committees of the following conferences:
ICALP '16,
APPROX '18,
WADS '19,
ESA '19
I have served as local organiser for several recent conferences, jointly held between QMUL and the London School of Economics:
Highlights of Algorithms (HALG 2022) and the Joint Two-Day Colloquiua in Combinatorics
(
2018,
2019,
2021
2022,
2023).
Publications
Journal Papers
-
Chien-Chung Huang, Justin Ward FPT-Algorithms for the l-Matchoid Problem with a Coverage Objective.
SIAM Journal on Discrete Mathematics. 37-2:1053-1078, 2023.
(Download from arXiv)
(Official Version via SIAM)
-
Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms.
SIAM Journal on Computing. 49-4:FOCS17-97--FOCS17-156, 2019.
(Download from arXiv)
(Official Version via SIAM)
-
Maxim Sviridenko, Jan Vondrák, Justin Ward. Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature.
Mathematics of Operations Research 42-4:897-1312, 2017.
(Download PDF)
(Official Version via INFORMS)
-
Marek Adamczyk, Maxim Sviridenko, and Justin Ward. Submodular Stochastic Probing on Matroids.
Mathematics of Operations Research 41-3:1022-1038, 2016.
(Download PDF)
(Official Version via INFORMS)
-
Justin Ward and Stanislav Živný. Maximizing k-Submodular Functions and Beyond.
ACM Transactions on Algorithms,
12-4:1--16, 2016.
(Download from arXiv)
(Official Version via ACM Digital Library)
-
Yuval Filmus and Justin Ward, A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint.
SIAM Journal on Computing, 43-2:514-542, 2014.
(Download PDF)
(Official Version via SIAM)
Conference Papers
-
Theophile Thiery and Justin Ward. An Improved Approximation for Maximum Weighted k-Set Packing.
2023 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1138--1162, 2023.
(Download from arXiv)
(Official version via SIAM)
-
Theophile Thiery and Justin Ward. Two-Sided Weak Submodularity for Matroid Constrained Optimization and Regression.
35th Conference on Learning Theory (COLT), PMLR 178:3605-3634, 2022.
(Download PDF)
-
Chien-Chung Huang, Theophile Thiery, Justin Ward. Improved multi-pass streaming algorithms for submodular maximization with matroid constraints.
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX), pp. 62:1-62:19, 2020.
(Download PDF)
-
Christopher Harshaw, Moran Feldman, Justin Ward, and Amin Karbasi.
Submodular Maximization Beyond Non-Negativity: Guarantees, Fast Algorithms, and Applications
36th International Conference on Machine Learning (ICML), PMLR 97:2634-2643, 2019.
(Download PDF)
-
Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward.
Better Guarantees for k-Means and Euclidean k-Median by
Primal-Dual Algorithms.
58th IEEE Symposium on Foundations of Computer Science
(FOCS), pp. 61-72, 2017.
(arXiv link)
-
Rafael Barbosa, Alina Ene, Huy Le Nguyen, and Justin Ward. A New Framework for Distributed Submodular Maximization.
57th IEEE Symposium on Foundations of Computer Science
(FOCS), pp. 645-654, 2016.
(arXiv link)
-
Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko, Justin Ward. A bi-criteria approximation algorithm for k-Means.
19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pp. 14:1-14:20, 2016.
(Download PDF)
-
Rafael Barbosa, Alina Ene, Huy Le Nguyen, and Justin Ward. The Power of Randomization: Distributed Submodular Maximization on Massive Datasets.
32nd International Conference on Machine Learning (ICML), PMLR 37:1236-1244, 2015.
(Download PDF)
-
Maxim Sviridenko, Jan Vondrák, Justin Ward. Tight Bounds for Submodular and Supermodular Optimization with Bounded Curvature.
25th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1134-1148, 2015.
(arXiv link)
-
Marek Adamczyk, Maxim Sviridenko, and Justin Ward. Submodular Stochastic Probing on Matroids.
31st International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 29-40, 2014.
(Download PDF)
-
Justin Ward and Stanislav Živný. Maximizing Bisubmodular and k-Submodular Functions.
24th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1468-1481, 2014.
(Download PDF)
-
Maxim Sviridenko and Justin Ward. Large Neighborhood Local Search for the Maximum Set Packing Problem.
40th International Colloquium on Automata Languages and Programming (ICALP), pp. 792-803, 2013.
(arXiv link)
-
Yuval Filmus and Justin Ward A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint.
53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 659-668, 2012.
(Download PDF)
-
Justin Ward. A (k+ 3)/2-approximation algorithm for monotone submodular k-set packing and general k-exchange systems.
29th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 42-53, 2012.
(Download PDF)
-
Yuval Filmus and Justin Ward. The Power of Local Search: Maximum Coverage over a Matroid.
29th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 601-612, 2012.
(Download PDF)
-
Moran Feldman, Joseph (Seffi) Naor, Roy Schwartz, and Justin Ward, Improved approximations for k-exchange systems.
19th European Symposium on Algorithms (ESA), pp. 784-798, 2011.
(Download PDF)
-
Justin Ward, Garrin Kimmell, and Perry Alexander. Prufrock: a framework for constructing polytypic theorem provers.
20th IEEE/ACM International Conference on Automated Software Engineering (ASE), pp. 423-426, 2005.
Theses
- Justin Ward. Oblivious and Non-Oblivious Local Search for Combinatorial Optimization.
PhD Thesis, University of Toronto, 2012.
PDF version available here.
- Justin Ward. A Unified Model of Algorithm Design.
Masters Thesis, University of Toronto, 2007.