Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem

N. Guttmann-Beck*, R. Hassin, Samir Khuller, B. Raghavachari

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

48 Scopus citations

Abstract

Let G = (V, E) be a complete undirected graph with vertex set V, edge set E, and edge weights l(e) satisfying triangle inequality. The vertex set V is partitioned into clusters V1,..., Vk. The clustered traveling salesman problem is to compute a shortest Hamiltonian cycle (tour) that visits all the vertices, and in which the vertices of each cluster are visited consecutively. Since this problem is a generalization of the traveling salesman problem, it is NP-hard. In this paper we consider several variants of this basic problem and provide polynomial time approximation algorithms for them.

Original languageEnglish (US)
Pages (from-to)422-437
Number of pages16
JournalAlgorithmica (New York)
Volume28
Issue number4
DOIs
StatePublished - Dec 1 2000

Keywords

  • Approximation algorithms
  • Clustered traveling salesman
  • Traveling salesman problem

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem'. Together they form a unique fingerprint.

Cite this