Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem (Extended Abstract)

Nili Guttmann-Beck, Refael Hassin, Samir Khuller, Balaji Raghavachari

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

1 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 (CTSP) 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)
Title of host publicationFoundations of Software Technology and Theoretical Computer Science - 18th Conference, Proceedings
Pages6-17
Number of pages12
DOIs
StatePublished - Dec 1 1998
Event18th Foundations of Software Technology and Theoretical Computer Science Conference, FST and TCS 1998 - Chennai, India
Duration: Dec 17 1998Dec 19 1998

Publication series

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

Conference

Conference18th Foundations of Software Technology and Theoretical Computer Science Conference, FST and TCS 1998
CountryIndia
CityChennai
Period12/17/9812/19/98

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

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

Cite this