Approximating the metric 2-peripatetic salesman problem

Approximating the metric 2-peripatetic salesman problem

0.00 Avg rating0 Votes
Article ID: iaor20105461
Volume: 5
Issue: 1
Start Page Number: 13
End Page Number: 20
Publication Date: Jan 2010
Journal: Algorithmic Operations Research
Authors: , ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.