An approximation algorithm for a bottleneck traveling salesman problem

Ming-Yang Kao*, Manan Sanghi

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 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)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.

Original languageEnglish (US)
Title of host publicationAlgorithms and Complexity - 6th Italian Conference, CIAC 2006, Proceedings
PublisherSpringer Verlag
Pages223-235
Number of pages13
ISBN (Print)354034375X, 9783540343752
DOIs
StatePublished - Jan 1 2006
Event6th Italian Conference on Algorithms and Complexity, CIAC 2006 - Rome, Italy
Duration: May 29 2006May 31 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3998 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other6th Italian Conference on Algorithms and Complexity, CIAC 2006
CountryItaly
CityRome
Period5/29/065/31/06

Fingerprint

Traveling salesman problem
Approximation algorithms
Travelling salesman problems
Approximation Algorithms
Polynomials
Distance Metric
Approximation
Real-world Applications
Alternate
Polynomial-time Algorithm
Trucks
Polynomial time
NP-complete problem
Geometry

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Kao, M-Y., & Sanghi, M. (2006). An approximation algorithm for a bottleneck traveling salesman problem. In Algorithms and Complexity - 6th Italian Conference, CIAC 2006, Proceedings (pp. 223-235). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3998 LNCS). Springer Verlag. https://doi.org/10.1007/11758471_23
Kao, Ming-Yang ; Sanghi, Manan. / An approximation algorithm for a bottleneck traveling salesman problem. Algorithms and Complexity - 6th Italian Conference, CIAC 2006, Proceedings. Springer Verlag, 2006. pp. 223-235 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{58f4b62f09fc4d5480dcc1468697cdd0,
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)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.",
author = "Ming-Yang Kao and Manan Sanghi",
year = "2006",
month = "1",
day = "1",
doi = "10.1007/11758471_23",
language = "English (US)",
isbn = "354034375X",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "223--235",
booktitle = "Algorithms and Complexity - 6th Italian Conference, CIAC 2006, Proceedings",
address = "Germany",

}

Kao, M-Y & Sanghi, M 2006, An approximation algorithm for a bottleneck traveling salesman problem. in Algorithms and Complexity - 6th Italian Conference, CIAC 2006, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3998 LNCS, Springer Verlag, pp. 223-235, 6th Italian Conference on Algorithms and Complexity, CIAC 2006, Rome, Italy, 5/29/06. https://doi.org/10.1007/11758471_23

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

Algorithms and Complexity - 6th Italian Conference, CIAC 2006, Proceedings. Springer Verlag, 2006. p. 223-235 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3998 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - An approximation algorithm for a bottleneck traveling salesman problem

AU - Kao, Ming-Yang

AU - Sanghi, Manan

PY - 2006/1/1

Y1 - 2006/1/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)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.

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)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.

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

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

U2 - 10.1007/11758471_23

DO - 10.1007/11758471_23

M3 - Conference contribution

AN - SCOPUS:33746078429

SN - 354034375X

SN - 9783540343752

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 223

EP - 235

BT - Algorithms and Complexity - 6th Italian Conference, CIAC 2006, Proceedings

PB - Springer Verlag

ER -

Kao M-Y, Sanghi M. An approximation algorithm for a bottleneck traveling salesman problem. In Algorithms and Complexity - 6th Italian Conference, CIAC 2006, Proceedings. Springer Verlag. 2006. p. 223-235. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/11758471_23