A 2-Approximation Algorithm for the Metric 2-Peripatetic Salesman Problem

DOI10.1007/978-3-540-77918-6_9zbMath1130.90386OpenAlexW1605923078MaRDI QIDQ5443376

A. A. Ageev, Artem V. Pyatkin

Publication date: 20 February 2008

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77918-6_9

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (3)

Multi-start iterated local search for the periodic vehicle routing problem with time windows and time spread constraints on services ⋮ Safe and secure vehicle routing: a survey on minimization of risk exposure ⋮ Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph

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
• A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
• Bounds for the symmetric 2-peripatetic salesman problem
• Well-solved cases of the 2-peripatetic salesman problem
• Lower bounds for symmetricK-peripatetic salesman problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A 2-Approximation Algorithm for the Metric 2-Peripatetic Salesman Problem