An approximation algorithm for a bottleneck traveling salesman problem ?
Consider a truck running along a road. It picks up a load Li L i 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,,Ln L 1 ,  , L n is equivalent to solving the traveling salesman problem (TSP) where the cities correspond to the loads Li L i with coordinates (?i,?i) ( ? i , ? i ) and the distance from Li L i to Lj L j is given by ? ? i ? j f ( x ) d x if ?j??i ? j ? ? i and by ? ? j ? i g ( x ) d x 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) 655679]. 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 GilmoreGomory's open question for the bottleneck TSP, Operations Research Letters 31 (2003) 483491]. 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.
bottleneck traveling salesman problem job sequencing two-machine flowshop reconstructing from inaccurate adjacency nuclear magnetic resonance (nmr) spectroscopy