Skip to main content

Justin Ward

Justin Ward

Click to download my curriculum vitae.

Research Fellow


Department of Computer Science / Centre for Discrete Mathematics and its Applications (DIMAP)
University of Warwick
Coventry CV4 7AL
United Kingdom

Email: J dot D dot Ward at warwick dot ac dot uk

Office: Computer Science Building Room 221

Phone: +44 24 7652 3088

About Me


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.

Research Interests


  • 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


Past Courses

CS 254: Algorithmic Graph Theory

Program Commitees

ICALP 2016

Publications


  • R. Barbosa, A. Ene, H. Le Nguyen, J. Ward. “The Power of Randomization: Distributed Submodular Maximization on Massive Datasets.”
    To appear in ICML 2015.
    (arXiv)
  • 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.
    (arXiv)
  • 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.
    (pdf)
    Previous version in FOCS '12: Proc. of the IEEE 53rd Annual Symposium on Foundations of Computer Science, 2012, pp. 659-668.
    (arXiv)
  • 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.
    (pdf)
  • 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.
    (pdf)
  • 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.
    (arXiv)
  • 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.
    (pdf)
  • 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.
    (pdf)
  • 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.
    (pdf)
  • 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)