Department of Computer Science / Centre for Discrete Mathematics and its Applications (DIMAP)
University of Warwick
Coventry CV4 7AL
Email: J dot D dot Ward at warwick dot ac dot uk
Office: Computer Science Building Room 221
Phone: +44 24 7652 3088
I study the general area of algorithm design and analysis, with a focus on approximation algorithms. I'm interested in formalizations of general algorithmic paradigms, such as greedy, dynamic programming, and especially local search.
More concretely, I study limitations and applications of local search algorithms with an emphasis on non-oblivious local search. My research focuses on developing simple combinatorial algorithms with improved approximation ratios by using local search and identifying and characterizing classes of problems for which local search performs well.
- Approximation algorithms for combinatorial optimization problems
- Design and analysis of local search algorithms
- Matroids and independence systems
- Models of algorithmic paradigms
- Information-theoretic limits on approximation performance of algorithmic paradigms
Teaching and Service
Program CommiteesICALP 2016
- R. Barbosa, A. Ene, H. Le Nguyen, J. Ward. “The Power of Randomization: Distributed Submodular Maximization on Massive Datasets.”
To appear in ICML 2015.
- M. Sviridenko, J. Vondrak, J. Ward. “Tight Bounds for Submodular and Supermodular Optimization with Bounded Curvature.”
In SODA '15: Proc. of the 25th ACM-SIAM Symposium on Discrete Algorithms, 2015, pp. 1134-1148.
- Y. Filmus and J. Ward, "A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint."
SIAM Journal on Computing 43-2 (2014), pp. 514-542.
Previous version in FOCS '12: Proc. of the IEEE 53rd Annual Symposium on Foundations of Computer Science, 2012, pp. 659-668.
- M. Adamczyk, M. Sviridenko, J. Ward. “Submodular Stochastic Probing on Matroids.”
In STACS '14: Proc. of the 31st International Symposium on Theoretical Aspects of Computer Science, 2014, pp. 29-40.
- J. Ward and S. Živný. “Maximizing Bisubmodular and k-Submodular Functions.”
In SODA '14: Proc. of the 24th ACM-SIAM Symposium on Discrete Algorithms, 2014, pp. 1468-1481.
- M. Sviridenko and J. Ward, "Large Neighborhood Local Search for the Maximum Set Packing Problem."
In ICALP '13: Proc. of the 40th International Colloquium on Automata Languages and Programming, 2013, pp. 792-803.
- J. Ward, "A (k+ 3)/2-approximation algorithm for monotone submodular k-set packing and general k-exchange systems."
In STACS '12: Proc. of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012, pp. 42-53.
- Y. Filmus and J. Ward, "The Power of Local Search: Maximum Coverage over a Matroid."
In STACS '12: 29th International Symposium on Theoretical Aspects of Computer Science, 2012, pp. 601-612.
- M. Feldman, J. Naor, R. Schwartz, and J. Ward, "Improved approximations for k-exchange systems."
In ESA '11: Proceedings of the 19th European Symposium on Algorithms, 2011, pp. 784-798.
- J. Ward, G. Kimmell, and P. Alexander, "Prufrock: a framework for constructing polytypic theorem provers."
In ASE '05: Proceedings of the 20th IEEE/ACM International Conference on Automated Software Engineering, 2005, pp. 423-426.
(ACM Digital Library)