## Abstract

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_{1}, ..., 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) d x if β_{j} ≥ α_{i} and by ∫_{βj}^{αi} g (x) d x if β_{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 + γ) where γ ≥ frac(f (x), g (x)) ≥ frac(1, γ) ∀ x. Note that when f (x) = g (x), the approximation ratio is 3.

Original language | English (US) |
---|---|

Pages (from-to) | 315-326 |

Number of pages | 12 |

Journal | Journal of Discrete Algorithms |

Volume | 7 |

Issue number | 3 |

DOIs | |

State | Published - Sep 2009 |

## Keywords

- Bottleneck traveling salesman problem
- Job sequencing
- Nuclear magnetic resonance (NMR) spectroscopy
- Reconstructing from inaccurate adjacency
- Two-machine flowshop

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics