Name
Title | ||
|---|---|---|
On Asymptotically Optimal Approach To The M-Peripatetic Salesman Problem On Random Inputs |
Abstract | ||
|---|---|---|
We study the m-Peripatetic Salesman Problem on random inputs. In earlier papers we proposed a polynomial asymptotically optimal algorithm for the m-PSP with different weight functions on random inputs. The probabilistic analysis carried out for that algorithm is not suitable in the case of the m-PSP with identical weight functions.In this paper we present an approach which under certain conditions gives polynomial asymptotically optimal algorithms for the m-PSP on random inputs with identical weight functions and for the m-PSP with different weight functions, as well. We describe in detail the cases of uniform and shifted exponential distributions of random inputs. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/978-3-319-44914-2_11 | DISCRETE OPTIMIZATION AND OPERATIONS RESEARCH, DOOR 2016 |
Keywords | DocType | Volume |
m-PSP, Asymptotically optimal algorithm, Performance guarantees, Random inputs, Uniform distribution, Shifted exponential distribution | Conference | 9869 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
2 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Edward Kh. Gimadi | 1 | 0 | 0.34 |
| Alexey M. Istomin | 2 | 0 | 0.34 |
| O. Yu. Tsidulko | 3 | 1 | 2.85 |