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

DOI10.1134/S0081543815050077zbMATH Open1336.90073OpenAlexW2473151934MaRDI QIDQ492278FDOQ492278

Authors: A. M. Istomin, I. A. Rykov, O. Yu. Tsidulko, Eh. 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

Recommendations

• Probabilistic analysis of an approximation algorithm for the traveling salesman problem on unbounded from above instances
• An asymptotically optimal algorithm for the \(m\)-peripatetic salesman problem on random inputs with discrete distribution
• On asymptotically optimal approach to the m-Peripatetic Salesman problem on random inputs
• scientific article; zbMATH DE number 808804
• An approximation algorithm for the minimum 2-peripatetic salesman problem with different weight functions

zbMATH Keywords

approximation algorithmexponential distributiondensity functionasymptotic optimalitytime complexitytruncated normal distributionrandom instances\(m\)-peripatetic salesman problem

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• The traveling salesman problem and its variations
• Title not available (Why is that?)
• Title not available (Why is that?)
• A branch and bound algorithm for symmetric 2-peripatetic salesman problems
• On some probability inequalities for some discrete optimization problems
• Title not available (Why is that?)
• Probabilistic analysis of an algorithm for the \(m\)-planar 3-index assignment problem on single-cycle permutations on one-cycle permutations
• On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space
• On Random Symmetric Travelling Salesman Problems
• Title not available (Why is that?)

Cited In (6)

• On asymptotically optimal approach to the m-Peripatetic Salesman problem on random inputs
• An asymptotically optimal algorithm for the \(m\)-peripatetic salesman problem on random inputs with discrete distribution
• On the \(m\)-capacitated peripatetic salesman problem with capacity restrictions
• Probabilistic analysis of an approximation algorithm for the traveling salesman problem on unbounded from above instances
• On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space
• Probabilistic analysis of an algorithm for the \(m\)-planar 3-index assignment problem on single-cycle permutations on one-cycle permutations

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q492278)