Paper Info
Title
Approximation Algorithms for the Maximum m-Peripatetic Salesman Problem.
Abstract
We consider the maximum m-Peripatetic Salesman Problem (MAX m-PSP), which is a natural generalization of the classic Traveling Salesman Problem. The problem is strongly NP-hard. In this paper we propose two polynomial approximation algorithms for the MAX m-PSP with different and identical weight functions, correspondingly. We prove that for random inputs uniformly distributed on the interval [a,b] these algorithms are asymptotically optimal for m = o(n). This means that with high probability their relative errors tend to zero as the number n of the vertices of the graph tends to infinity. The results remain true for the distributions of inputs that minorize the uniform distribution.
Year
DOI
Venue
2017
10.1007/978-3-319-73013-4_28
ANALYSIS OF IMAGES, SOCIAL NETWORKS AND TEXTS, AIST 2017
Keywords
DocType
Volume
Maximum m-Peripatetic Salesman Problem,Time complexity,Edge-disjoint Hamiltonian cycles
Conference
10716
ISSN
Citations 
PageRank 
0302-9743
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
E. Kh. Gimadi111.83
O. Yu. Tsidulko212.85