Coauthor: Mordecai Golin and Wei Yu

We consider a generalization of the Traveling Salesman Problem, in which each city is associated with a release time and a service time. The salesman has to visit each city at or after its release time. We show an approximation algorithm with performance ratio better than 5/2 when the number of distinct release times is fixed. Then we analyze a natural class of algorithms and prove that no performance ratio better than 5/2 is possible unless the Metric TSP can be approximated with a ratio strictly less than 3/2. Finally, we consider a special case of VSP, that has a heavy edge, and present an approximation algorithm with performance ratio less than 5/2 as well.