An approximation algorithm for a bottleneck traveling salesman problem

Consider a truck running along a road. It picks up a load LiLi at point βiβi and delivers it at αiα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)f(x) and that in the other direction is given by g(x)g(x). Minimizing the total time spent to deliver loads L1,…,LnL1,…,Ln is equivalent to solving the traveling salesman problem (TSP) where the cities correspond to the loads LiLi with coordinates (αi,βi)(αi,βi) and the distance from LiLi to LjLj is given by ∫αiβjf(x)dx if βj⩾αiβj⩾αi and by ∫βjαig(x)dx if βj<αiβj<αi.Gilmore and Gomory obtained a polynomial time solution for this TSP [P.C. Gilmore, R.E. Gomory, Sequencing a one state-variable machine: A solvable case of the traveling salesman problem, Operations Research 12 (1964) 655–679]. However, the bottleneck version of the problem (BTSP) was left open. Recently, Vairaktarakis showed that BTSP with this distance metric is NP-complete [G.L. Vairaktarakis, On Gilmore–Gomory's open question for the bottleneck TSP, Operations Research Letters 31 (2003) 483–491]. We provide an approximation algorithm for this BTSP by exploiting the underlying geometry in a novel fashion. We achieve an approximation ratio of (2+γ)(2+γ) where γ⩾f(x)g(x)⩾1γ∀x. Note that when f(x)=g(x)f(x)=g(x), the approximation ratio is 3.