Contact Information
Email: jward AT cs DOT toronto DOT edu
Office: SF 4306E
University of Toronto
Department of Computer Science
Sandford Fleming Building
10 King's College Road
Toronto, Ontario M5S 3G4
Canada
About Me
I am a PhD student at the University of Toronto under the supervision of Allan Borodin in the Department of Computer Science.
I am interested in the general area of algorithm design and analysis. I'm interested in formalizations of general algorithmic paradigms, such as greedy, dynamic programming, and 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.
Publications
- Y. Filmus and J. Ward, "A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint."
Submitted to FOCS '12.
(arXiv) - J. Ward, "A (k+ 3)/2-approximation algorithm for monotone submodular k-set packing and general k-exchange systems."
In STACS '12: 29th International Symposium on Theoretical Aspects of Computer Science, 2012, vol. 14, 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, vol. 14, 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)