An approximation algorithm for a bottleneck traveling salesman problem

Consider a truck running along a road. It picks up a load L_i at point β_i and delivers it at α_i, carrying at most one load at a time. The speed on the various parts of the road in one direction is given by f(x) and that in the other direction is given by g(x). Minimizing the total time spent to deliver loads L₁,...,L_n is equivalent to solving the Traveling Salesman Problem (TSP) where the cities correspond to the loads L_i with coordinates (α_i, β_i) and the distance from L_i to L_j is given by ∫_αi^βj f(x)dx if β_j ≥ α_i and by ∫_βj^αi g(x)dx if β_j < α_i. This case of TSP is polynomially solvable with significant real-world applications. Gilmore and Gomory obtained a polynomial time solution for this TSP [6]. However, the bottleneck version of the problem (BTSP) was left open. Recently, Vairaktarakis showed that BTSP with this distance metric is NP-complete [10]. We provide an approximation algorithm for this BTSP by exploiting the underlying geometry in a novel fashion. This also allows for an alternate analysis of Gilmore and Gomory's polynomial time algorithm for the TSP. We achieve an approximation ratio of (2 + γ) where γ ≥ f(x)/g(x) ≥ 1/γ ∀x. Note that when f(x) = g(x), the approximation ratio is 3.