Approximation algorithms for the maximum 2-peripatetic salesman problem

DOI10.1134/S1990478912030040zbMath1324.90133MaRDI QIDQ5263758

E. V. Ivonina, E. Kh. Gimadi

Publication date: 17 July 2015

Published in: Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

zbMATH Keywords

traveling salesman problempolynomial algorithmguaranteed approximation ratio2-peripatetic salesman problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (5)

A polynomial algorithm with asymptotic ratio $2/3$ for the asymmetric maximization version of the $m$-PSP ⋮ Safe and secure vehicle routing: a survey on minimization of risk exposure ⋮ An asymptotically optimal algorithm for the m-Peripatetic Salesman Problem on random inputs with discrete distribution ⋮ Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph ⋮ A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP

This page was built for publication: Approximation algorithms for the maximum 2-peripatetic salesman problem