Approximation Algorithms

True to the game.

Although I no longer work heavily in this area, my thesis research was in approximation algorithms for routing problems. Perhaps the most famous such problem is the Traveling Salesman Problem (TSP), in which the goal is to visit all locations and return to the starting point with the minimum effort expended.

Although the TSP is already an NP-hard optimization problem, my work focuses on even more challenging versions of the problem in which locations can only be visited during predetermined time windows.

Selected Publications

• G. N. Frederickson and B. Wittman. Approximation Algorithms for the Traveling Repairman and Speeding Deliveryman Problems. In Algorithmica, volume 62, numbers 3-4, pages 1198-1221. Springer, 2012.
  Available http://link.springer.com/article/10.1007%2Fs00453-011-9515-4


• G. N. Frederickson and B. Wittman. Speedup in the Traveling Repairman Problem with Constrained Time Windows. 2011.
  Available arXiv:1101.3960


• G. N. Frederickson and B. Wittman. Two Multivehicle Routing Problems with Unit-Time Windows. 2011.
  Available arXiv:1101.3953


• G. N. Frederickson and B. Wittman. Approximation Algorithms for the Traveling Repairman and Speeding Deliveryman Problems with Unit-Time Windows. In Approximation, Randomization, and Combinatorial Optimization, volume 4627 of LNCS, pages 119-133. Springer, 2007.
  Available http://link.springer.com/chapter/10.1007%2F978-3-540-74208-1_9

Thesis

Approximation algorithms for time-constrained vehicle routing problems
Purdue University, 2008.
Available http://docs.lib.purdue.edu/dissertations/AAI3373260/