The aim of this paper is to investigate the approximability of some generalized versions of
TSP which typically arise in practical applications. The most important generalization is
TSP with time windows, where some vertices have to be visited after some specified opening time, but before some deadline. Our
main results are as follows (assuming
P ≠
NP).
1. In contrast to the constant approximability of metric TSP, there is no polynomial-time o(|V|)-approximation algorithm for metric TSP with time windows.
2. Metric TSP with as few as two time windows is not approximable within ratio 2–ε.
3. There is no polynomial-time o(|V|)-approximation algorithm for TSP with a single time window and arbitrarily small violations of the triangle inequality.
4. Metric TSP with a prescribed linear order on some vertices can be solved in polynomial time with a constant approximation
guarantee, even if the triangle inequality is violated by a constant factor.
Keywords TSP with time windows - approximation - inapproximability
This work was partially supported by SNF grant 200021-109252/1. A full version of Section 3 will appear in Theory of Computing Systems [7].