Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2

DOI10.1016/j.dam.2008.06.025zbMath1169.90466OpenAlexW1979466622MaRDI QIDQ1026101

E. Kh. Gimadi, Vangelis Th. Paschos, Yu. V. Glazkov, Alexei E. Baburin, Frederico Della Croce

Publication date: 24 June 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.06.025

zbMATH Keywords

matchingapproximationfactor2-peripatetic salesman problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation algorithms (68W25)

Related Items

Approximability of the minimum-weight \(k\)-size cycle cover problem ⋮ Safe and secure vehicle routing: a survey on minimization of risk exposure ⋮ On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space ⋮ A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph ⋮ Approximability of the problem about a minimum-weight cycle cover of a graph ⋮ Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph ⋮ Time complexity analysis of evolutionary algorithms for 2-hop \((1,2)\)-minimum spanning tree problem ⋮ The undirected \(m\)-capacitated peripatetic salesman problem

Cites Work

• Branch-and-cut algorithms for the undirected \(m\)-Peripatetic Salesman Problem
• A branch and bound algorithm for symmetric 2-peripatetic salesman problems
• A heuristic approach to the overnight security service problem
• 8/7-approximation algorithm for (1,2)-TSP
• Bounds for the symmetric 2-peripatetic salesman problem
• Well-solved cases of the 2-peripatetic salesman problem
• The Traveling Salesman Problem with Distances One and Two
• Lower bounds for symmetricK-peripatetic salesman problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item