An asymptotically optimal algorithm for the m-Peripatetic Salesman Problem on random inputs with discrete distribution

DOI10.1134/S1990478917030061zbMath1399.05210OpenAlexW2753301622MaRDI QIDQ5374000

O. Yu. Tsidulko, E. Kh. Gimadi

Publication date: 6 April 2018

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

Full work available at URL: https://doi.org/10.1134/s1990478917030061

zbMATH Keywords

asymptotically optimal algorithmdiscrete distribution\(m\)-peripatetic salesman problemrandom input

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (max. 100)

Safe and secure vehicle routing: a survey on minimization of risk exposure

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Probabilistic analysis of an approximation algorithm for the \(m\)-peripatetic salesman problem on random instances unbounded from above
• Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph
• On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• An algorithm for finding Hamilton paths and cycles in random graphs
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Hamiltonian circuits in random graphs
• A branch and bound algorithm for symmetric 2-peripatetic salesman problems
• An Algorithm with Approximation Ratio 5/6 for the Metric Maximum m-PSP
• An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three
• An algorithm for finding hamilton cycles in random directed graphs
• Bounds for the symmetric 2-peripatetic salesman problem
• Well-solved cases of the 2-peripatetic salesman problem
• Approximation algorithms for the maximum 2-peripatetic salesman problem
• Probabilistic analysis of an algorithm for the m-planar 3-index assignment problem on single-cycle permutations
• Lower bounds for symmetricK-peripatetic salesman problems

This page was built for publication: An asymptotically optimal algorithm for the m-Peripatetic Salesman Problem on random inputs with discrete distribution