Approximating the Metric 2-Peripatetic Salesman Problem
Calvo, Roberto Wolfler; Paschos, Vangelis; Della Croce, Federico (2010), Approximating the Metric 2-Peripatetic Salesman Problem, Algorithmic Operations Research, 5, 1, p. 13-20
TypeArticle accepté pour publication ou publié
Journal nameAlgorithmic Operations Research
Preeminent Academic Facets Inc.
MetadataShow full item record
Abstract (EN)This paper deals with the 2-Peripatetic Salesman Problem for the case where costs respect the triangle inequality. The aim is to determine 2 edge disjoint Hamiltonian cycles of minimum total cost on a graph. We first present a straightforward 9/4 approximation algorithm based on the well known Christofides algorithm for the travelling salesman problem. Then we propose a 2(n-1)/n-approximation polynomial time algorithm based on the solution of the minimum cost two-edge-disjoint spanning trees problem. Finally, we show that by partially combining these two algorithms, a 15/8 approximation ratio can be reached if a 5/4 approximation algorithm can be found for the related problem of finding two edge disjoint subgraphs consisting in a spanning tree and an hamiltonian cycle of minimum total cost.
Subjects / KeywordsApproximation; 2-peripatetic salesman problem
Showing items related by title and author.
Baburin, Aleksei; Della Croce, Federico; Gimadi, Edward; Glazkov, Yuri; Paschos, Vangelis (2009) Article accepté pour publication ou publié
Lower bounds on the approximation ratios of leading heuristics for the single machine total tardiness problem Grosso, Andrea; Della Croce, Federico; Paschos, Vangelis (2004) Article accepté pour publication ou publié