Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419354 | Discrete Applied Mathematics | 2014 | 6 Pages |
Abstract
We consider the maximum traveling salesman problem (Max TSP) and the maximum mm-peripatetic salesman problem (Max m-PSP) on assuming that the vertices of a graph lie in some geometric space. For the both problems we obtain approximation algorithms that find asymptotically optimal solutions in the case of a normed space with a bounded dimension and in the case of a polyhedral space with a bounded number of facets, respectively.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
V.V. Shenmaier,