| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 418035 | Discrete Applied Mathematics | 2015 | 8 Pages |
Abstract
In this paper we present two new polynomial algorithms for the asymmetric version of the mm-Peripatetic Salesman Problem (mm-APSP) which consists in finding m edge-disjoint Hamiltonian circuits of extremal total weight in a complete weighted digraph. The first algorithm solves the asymmetric 2-PSP on maximum. Its approximation ratio is equal to 2/3. The second algorithm deals with the minimization version of the asymmetric m-PSP on random instances. For this algorithm conditions for asymptotically exactness are presented.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
E.Kh. Gimadi, A.N. Glebov, A.A. Skretneva, O.Yu. Tsidulko, D.Zh. Zambalaeva,