Approximation Algorithms for the Traveling Repairman and Speeding Deliveryman Problems

Greg N. Frederickson, Barry Wittman

Constant-factor, polynomial-time approximation algorithms are presented for two variations of the traveling salesman problem with time windows. In the first variation, the travelin…