An approximation algorithm for a bottleneck traveling salesman problem

Ming-Yang Kao*, Manan Sanghi

*Corresponding author for this work

Research output: Contribution to journalArticle

9 Citations (Scopus)

Abstract

Consider a truck running along a road. It picks up a load Li 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 L1, ..., Ln is equivalent to solving the traveling salesman problem (TSP) where the cities correspond to the loads Li with coordinates (αi, βi) and the distance from Li to Lj 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 languageEnglish (US)
Pages (from-to)315-326
Number of pages12
JournalJournal of Discrete Algorithms
Volume7
Issue number3
DOIs
StatePublished - Sep 1 2009

Fingerprint

Traveling salesman problem
Approximation algorithms
Travelling salesman problems
Approximation Algorithms
Operations research
Operations Research
Distance Metric
Approximation
Trucks
Sequencing
Polynomial time
NP-complete problem
Polynomials
Geometry

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

Cite this

@article{dabda03eb51c47da87178496a11c421f,
title = "An approximation algorithm for a bottleneck traveling salesman problem",
abstract = "Consider a truck running along a road. It picks up a load Li 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 L1, ..., Ln is equivalent to solving the traveling salesman problem (TSP) where the cities correspond to the loads Li with coordinates (αi, βi) and the distance from Li to Lj 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.",
keywords = "Bottleneck traveling salesman problem, Job sequencing, Nuclear magnetic resonance (NMR) spectroscopy, Reconstructing from inaccurate adjacency, Two-machine flowshop",
author = "Ming-Yang Kao and Manan Sanghi",
year = "2009",
month = "9",
day = "1",
doi = "10.1016/j.jda.2008.11.007",
language = "English (US)",
volume = "7",
pages = "315--326",
journal = "Journal of Discrete Algorithms",
issn = "1570-8667",
publisher = "Elsevier",
number = "3",

}

An approximation algorithm for a bottleneck traveling salesman problem. / Kao, Ming-Yang; Sanghi, Manan.

In: Journal of Discrete Algorithms, Vol. 7, No. 3, 01.09.2009, p. 315-326.

Research output: Contribution to journalArticle

TY - JOUR

T1 - An approximation algorithm for a bottleneck traveling salesman problem

AU - Kao, Ming-Yang

AU - Sanghi, Manan

PY - 2009/9/1

Y1 - 2009/9/1

N2 - Consider a truck running along a road. It picks up a load Li 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 L1, ..., Ln is equivalent to solving the traveling salesman problem (TSP) where the cities correspond to the loads Li with coordinates (αi, βi) and the distance from Li to Lj 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.

AB - Consider a truck running along a road. It picks up a load Li 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 L1, ..., Ln is equivalent to solving the traveling salesman problem (TSP) where the cities correspond to the loads Li with coordinates (αi, βi) and the distance from Li to Lj 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.

KW - Bottleneck traveling salesman problem

KW - Job sequencing

KW - Nuclear magnetic resonance (NMR) spectroscopy

KW - Reconstructing from inaccurate adjacency

KW - Two-machine flowshop

UR - http://www.scopus.com/inward/record.url?scp=67349171914&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=67349171914&partnerID=8YFLogxK

U2 - 10.1016/j.jda.2008.11.007

DO - 10.1016/j.jda.2008.11.007

M3 - Article

AN - SCOPUS:67349171914

VL - 7

SP - 315

EP - 326

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

SN - 1570-8667

IS - 3

ER -