Approximating the metric 2-Peripatetic Salesman Problem

Authors

  • Federico Della Croce DAI Politecnico di Torino, Italy
  • Vangelis Th. Paschos LAMSADE - CNRS UMR 7024 and Université Paris Dauphine, France
  • Roberto Wolfler Calvo LIPN - Université PARIS 13, France

Keywords:

Peripatetic salesman, approximation algorithm

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.

Downloads

Published

2010-04-14

How to Cite

Della Croce, F., Paschos, V. T., & Calvo, R. W. (2010). Approximating the metric 2-Peripatetic Salesman Problem. Algorithmic Operations Research, 5(1), Pages 13 – 20. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/11496

Issue

Vol. 5 No. 1 (2010)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.