Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00478
Approximation Algorithms for Not Necessarily Disjoint Clustered TSP
Nili GuttmannBeck,
Eyal Knaan, and
Michal Stern
Vol. 22, no. 4, pp. 555575, 2018. Regular paper.
Abstract Let $G=(V,E)$ be a complete undirected graph with vertex set $V$, edge set $E$ and let $H = \langle G,\mathcal{S} \rangle $ be a hypergraph, where $\mathcal{S}$ is a set of not necessarily disjoint clusters $S_1,\ldots,S_m$, $S_i \subseteq V$ $\forall i \in \{ 1,\ldots,m \}$. The clustered traveling salesman problem CTSP is to compute a shortest Hamiltonian path that visits each one of the vertices once, such that the vertices of each cluster are visited consecutively.
In this paper, we present a 4approximation algorithm for the general case. When the intersection graph is a path, we present a 5/3approximation algorithm. When the clusters' sizes are all bounded by a constant and the intersection graph is connected, we present an optimal polynomial time algorithm.

Submitted: June 2017.
Reviewed: June 2018.
Revised: September 2018.
Accepted: September 2018.
Final: September 2018.
Published: September 2018.
Communicated by
Susanne Albers

Journal Supporters
