Geodesic
Approximation Algorithms for Not Necessarily Disjoint Clustered TSP
Journal of Graph Algorithms and Applications, Tome 22 (2018) no. 4, pp. 555-575.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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 4-approximation algorithm for the general case. When the intersection graph is a path, we present a 5/3-approximation algorithm. When the clusters' sizes are all bounded by a constant and the intersection graph is connected, we present an optimal polynomial time algorithm. 
@article{JGAA_2018_22_4_a0,
     author = {Nili Guttmann-Beck and Eyal Knaan and Michal Stern},
     title = {Approximation {Algorithms} for {Not} {Necessarily} {Disjoint} {Clustered} {TSP}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {555--575},
     publisher = {mathdoc},
     volume = {22},
     number = {4},
     year = {2018},
     doi = {10.7155/jgaa.00478},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00478/}
}
TY  - JOUR
AU  - Nili Guttmann-Beck
AU  - Eyal Knaan
AU  - Michal Stern
TI  - Approximation Algorithms for Not Necessarily Disjoint Clustered TSP
JO  - Journal of Graph Algorithms and Applications
PY  - 2018
SP  - 555
EP  - 575
VL  - 22
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00478/
DO  - 10.7155/jgaa.00478
LA  - en
ID  - JGAA_2018_22_4_a0
ER  - 
%0 Journal Article
%A Nili Guttmann-Beck
%A Eyal Knaan
%A Michal Stern
%T Approximation Algorithms for Not Necessarily Disjoint Clustered TSP
%J Journal of Graph Algorithms and Applications
%D 2018
%P 555-575
%V 22
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00478/
%R 10.7155/jgaa.00478
%G en
%F JGAA_2018_22_4_a0
Nili Guttmann-Beck; Eyal Knaan; Michal Stern. Approximation Algorithms for Not Necessarily Disjoint Clustered TSP. Journal of Graph Algorithms and Applications, Tome 22 (2018) no. 4, pp. 555-575. doi : 10.7155/jgaa.00478. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00478/

Cité par Sources :