Justin Ward
I am a Research Scientist in the theory group at the School of Computer and Communication Sciences at EPFL.
| Research | My research interests include approximation algorithms, combinatorial optimization, and submodularity. I am also interested in models of simple, combinatorial algorithms, such as local search and greedy algorithms, for general combinatorial optimization 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. |
For more information please see my CV.
| Phone | +41 21 693 75 82 |
| firstname.lastname at epfl dot ch |
|
| Address |
EPFL-IC Building INJ (INJ 131) Station 14 CH-1015 Lausanne Switzerland |
| Office | INJ131 |
Teaching and Service
Program Committees
I have recently served on the program committees of the following conferences: ICALP '16
Publications
Journal Papers
-
Maxim Sviridenko, Jan Vondrák, Justin Ward. Tight Bounds for Submodular and Supermodular Optimization with Bounded Curvature.
Accepted to Mathematics of Operations Research (to appear). -
Marek Adamczyk, Maxim Sviridenko, and Justin Ward. Submodular Stochastic Probing on Matroids.
Mathematics of Operations Research 41-3 (2016), pp. 1022–1038.
(arXiv link) -
Justin Ward and Stanislav Živný. Maximizing k-Submodular Functions and Beyond.
To appear in ACM Transactions on Algorithms.
(arXiv link) -
Yuval Filmus and Justin Ward, A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint.
SIAM Journal on Computing 43-2 (2014), pp. 514-542.
(Download PDF)
Conference Papers
-
Rafael Barbosa, Alina Ene, Huy Le Nguyen, and Justin Ward. A New Framework for Distributed Submodular Maximization.
In 57th IEEE Symposium on Foundations of Computer Science (FOCS), 2016.
(arXiv link) -
Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko, Justin Ward. A bi-criteria approximation algorithm for k-Means.
In 19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). 2016.
(Download PDF) -
Rafael Barbosa, Alina Ene, Huy Le Nguyen, and Justin Ward. The Power of Randomization: Distributed Submodular Maximization on Massive Datasets.
In 32nd International Conference on Machine Learning (ICML), 2015, pp. 1236-1244.
(Download PDF) -
Maxim Sviridenko, Jan Vondrák, Justin Ward. Tight Bounds for Submodular and Supermodular Optimization with Bounded Curvature.
In 25th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015, pp. 1134-1148.
(arXiv link) -
Marek Adamczyk, Maxim Sviridenko, and Justin Ward. Submodular Stochastic Probing on Matroids.
In 31st International Symposium on Theoretical Aspects of Computer Science (STACS), 2014, pp. 29-40.
(Download PDF) -
Justin Ward and Stanislav Živný. Maximizing Bisubmodular and k-Submodular Functions.
In 24th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014, pp. 1468-1481.
(Download PDF) -
Maxim Sviridenko and Justin Ward. Large Neighborhood Local Search for the Maximum Set Packing Problem.
In 40th International Colloquium on Automata Languages and Programming (ICALP), 2013, pp. 792-803.
(arXiv link) -
Yuval Filmus and Justin Ward A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint.
In 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2012, pp. 659-668.
(Download PDF) -
Justin Ward. A (k+ 3)/2-approximation algorithm for monotone submodular k-set packing and general k-exchange systems.
In 29th International Symposium on Theoretical Aspects of Computer Science (STACS), 2012, pp. 42-53.
(Download PDF) -
Yuval Filmus and Justin Ward. The Power of Local Search: Maximum Coverage over a Matroid.
In 29th International Symposium on Theoretical Aspects of Computer Science (STACS), 2012, pp. 601-612.
(Download PDF) -
Moran Feldman, Joseph (Seffi) Naor, Roy Schwartz, and Justin Ward, Improved approximations for k-exchange systems.
In 19th European Symposium on Algorithms (ESA), 2011, pp. 784-798.
(Download PDF) -
Justin Ward, Garrin Kimmell, and Perry Alexander. Prufrock: a framework for constructing polytypic theorem provers.
In 20th IEEE/ACM International Conference on Automated Software Engineering (ASE), 2005, pp. 423-426.
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.