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

• DBLP (organized by date and type)
• GoogleScholar (organized by citation count)
• Organized by topic:
  • Traveling Salesman Problem
  • Aggregating Inconsistent Information
  • Maximum Satisfiability
  • Network Design
  • Scheduling
  • Electronic Commerce
  • Permutations: Sorting and Shuffling

Traveling Salesman Problem

• Layers and matroids for the traveling salesman's paths, with Frans Schalekamp, András Sebő and Vera Traub. In Oper. Res. Lett. 46(1): 60-63 (2018) .
• The Salesman's Improved Paths: A 3/2+1/34 Approximation, with András Sebő. FOCS 2016. Journal version to appear in J.ACM. Slides.
• Improved Approximations for Cubic and Cubic Bipartite TSP. in Math. Program. 172(1-2): 399-413 (2018). Preliminar version appeared in IPCO 2016: 250-261. Slides.
• On the Integrality Gap of the Subtour LP for the 1,2-TSP with Jiawei Qian, Frans Schalekamp and David P. Williamson. in Math. Program. 150(1): 131-151 (2015). Preliminary version appeared in LATIN 2012: 606-617.
• 2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture with Frans Schalekamp and David P. Williamson. Math. Oper. Res. 39(2): 403-417 (2014). Preliminary version A Proof of the Boyd-Carr Conjecture appeared in SODA 2012.
• Toward a precise integrality gap for triangle-free 2-matchings with Philipp Klodt. CTW 2013: 151-154
• Simpler Approximation of the Maximum Asymmetric Traveling Salesman Problem with Katarzyna Paluch and Khaled Elbassioni. STACS 2012.
• Multiplying Pessimistic Estimators: Deterministic Approximation of Max TSP and Maximum Triangle Packing. Discrete Applied Mathematics 161(13-14): 2142-2157 (2013). Preliminary version appeared in COCOON 2010.

Aggregating Inconsistent Information

• 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.

Maximum Satisfiability

• Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds, with Matthias Poloczek, Georg Schnitger, David P. Williamson. In SIAM J. Comput. 46(3): 1029-1061 (2017)
• On Some Recent MAX SAT Approximation Algorithms with Matthias Poloczek and David P. Williamson. LATIN 2014: 598-609.
• Simpler 3/4-approximation algorithms for MAX SAT. WAOA 2011.

Network Design

• Deterministic Sampling Algorithms for Network Design. Algorithmica 60(1): 110-151 (2011), Special Issue on European Symposium on Algorithms. Journal version of Deterministic Sampling Algorithms for Network Design. European Symposium on Algorithms (ESA), 2008. (Winner of Best Student Paper Award (Track A)). 
•  A simpler and better derandomization of an approximation algorithm for Single Source Rent-or-Buy with David P. Williamson. Operations Research Letters, Volume 35, Issue 6, Pages 707-712.

Scheduling

• Minimizing worst-case and average-case makespan over scenarios, with Esteban Feuerstein, Alberto Marchetti-Spaccamela, Frans Schalekamp, Rene Sitters, Suzanne van der Ster, Leen Stougie. In J. Scheduling 20(6): 545-555 (2017). Preliminary version appeared in COCOON 2014: 559-571.
• Split scheduling with uniform setup times with Frans Schalekamp, Rene Sitters, Suzanne van der Ster, Leen Stougie and Victor Verdugo. J. Scheduling 18(2): 119-129 (2015).
• An improved monotone algorithm for scheduling related machines with precedence constraints. Oper. Res. Lett. 39(6): 423-427 (2011).

Electronic Commerce

• Maximizing influence in a competitive social network: a follower's perspective with Tim Carnes, Chandrashekhar Nagarajan, and Stefan M. Wild. ICEC '07 Proceedings of the ninth international conference on Electronic commerce, 2007

Permutations: Sorting and Card Shuffling

• An Upper Bound on the Number of Circular Transpositions to Sort a Permutation with James Bieron, Frans Schalekamp and Gexin Yu. Inf. Process. Lett. 116(11): 718-722 (2016).
• The Achilles' Heel of the GSR Shuffle: A Note On New Age Solitaire with Frans Schalekamp. Probability in the Engineering and Informational Sciences, Volume 18 , Issue 3 (July 2004)
• Partitio et Emergo: A Note on Computation of Eigenvalues of a Shuffle Matrix with Frans Schalekamp. Unpublished manuscript.
• Master's thesis: Over het schudden van kaarten (In Dutch) with Frans Schalekamp. August 2000 - winner of VVS+OR-Thesis Award 2001 for best Dutch Master's thesis in Operations Research.