Research
Closing the Gap: Finding Better Algorithms and Better Bounds
My research interests are in combinatorial optimization.
I design and analyze algorithms for optimization problems arising in areas such as:
- information science, in particular, aggregating inconsistent structured information;
- network design, scheduling and logistics;
- computational biology.
For many problems of interest, finding optimal solutions is computationally intractable. My work specifically focuses on practical algorithms for approximately solving these problems, by leveraging techniques from:
- discrete mathematics, such as graph theory, combinatorics and matroid theory;
- computer science, such as complexity analysis, datastructures, and approximation algorithms;
- operations research, such as linear programming and network flows.
My work has been supported by a Simons Collaboration Grant for Mathematicians.
In addition to theoretical research, I work with undergraduate and graduate students on practical applications of Operations Research. In recent project, we used network optimization to optimize the matching of students and pre-major advisors at William & Mary.
Publications
- A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest, with
Neil Olver, Frans Schalekamp, Suzanne van der Ster, and Leen Stougie. Submitted.
- A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest with
Frans Schalekamp and Suzanne van der Ster.
ICALP 2016.
- Improved Approximation Algorithms for Bipartite Correlation Clustering with Nir Ailon, Noa Avigdor-Elgrabli and Edo Liberty.
SIAM J. Comput. 41(5): 1110-1121 (2012). Preliminary version appeared in
ESA 2011.
- Popular ranking with Frans Schalekamp and David P. Williamson. Discrete Applied Mathematics 165:312-316(2014). Preliminary version appeared in CTW 2011.
- Clustering with or without the approximation with J. Comb. Optim. 25(3): 393-429 (2013). Preliminary version appeared in COCOON 2010.
- Deterministic pivoting algorithms for constrained ranking and clustering problems with David P. Williamson. Mathematics of Operations Research, Vol. 34, No. 3, August 2009, pp. 594-620. Journal version combining part of the results in
Deterministic pivoting algorithms for constrained ranking and clustering problems with Rajneesh Hegde, Kamal Jain and David P. Williamson. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007, and the results in Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems with David P. Williamson. 5th Workshop on Approximation and Online Algorithms (WAOA), 2007.
- Linear Programming Based Approximation Algorithms for Feedback Set Problems in Bipartite Tournaments. Journal version, Theoretical Computer Science, Volume 412, Issue 23, 20 May 2011, Pages 2556-2561. Preliminary version appeared in
Conference on Theory and Applications of Models of Computation (TAMC), 2009.
- Rank Aggregation: Together We Are Strong with Frans Schalekamp. Workshop on Algorithm Engineering and Experiments (ALENEX), 2009.
|