Email this article An asymptotically optimal algorithm for the m-Peripatetic Salesman Problem on random inputs with discrete distribution
- Authors: Gimadi E.K.1,2, Tsidulko O.Y.1,2
-
Affiliations:
- Sobolev Institute of Mathematics
- Novosibirsk State University
- Issue: Vol 11, No 3 (2017)
- Pages: 354-361
- Section: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/212776
- DOI: https://doi.org/10.1134/S1990478917030061
- ID: 212776
Cite item
Open Access
Access granted
Subscription Access
Abstract
We consider the m-Peripatetic Salesman Problem (m-PSP) on random inputs with discrete distribution function. In this paper we present a polynomial approximation algorithm which, under certain conditions, with high probability (w.h.p.) gives optimal solution for both the m-PSP on random inputs with identical weight functions and the m-PSP with different weight functions.
About the authors
E. Kh. Gimadi
Sobolev Institute of Mathematics; Novosibirsk State University
Author for correspondence.
Email: gimadi@math.nsc.ru
Russian Federation, pr. Akad. Koptyuga 4, Novosibirsk, 630090; ul. Pirogova 2, Novosibirsk, 630090
O. Yu. Tsidulko
Sobolev Institute of Mathematics; Novosibirsk State University
Email: gimadi@math.nsc.ru
Russian Federation, pr. Akad. Koptyuga 4, Novosibirsk, 630090; ul. Pirogova 2, Novosibirsk, 630090
Supplementary files
