Probabilistic analysis of an approximation algorithm for the \(m\)-peripatetic salesman problem on random instances unbounded from above

DOI10.1134/S0081543815050077zbMath1336.90073OpenAlexW2473151934MaRDI QIDQ492278

A. M. Istomin, I. A. Rykov, O. Yu. Tsidulko, E. Kh. Gimadi

Publication date: 20 August 2015

Published in: Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

exponential distributionapproximation algorithmdensity functiontime complexityasymptotic optimalitytruncated normal distributionrandom instances\(m\)-peripatetic salesman problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Stochastic programming (90C15) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (1)

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

Cites Work

• On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space
• A branch and bound algorithm for symmetric 2-peripatetic salesman problems
• The traveling salesman problem and its variations
• Probabilistic analysis of an algorithm for the m-planar 3-index assignment problem on single-cycle permutations
• On Random Symmetric Travelling Salesman Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Probabilistic analysis of an approximation algorithm for the \(m\)-peripatetic salesman problem on random instances unbounded from above