On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space
type: Item
instance of: scholarly article
title: On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space
zbMATH Open document ID: 1230.65065
DOI: 10.1134/S0081543811020015
author: Eh. Kh. Gimadi
author: Alexei E. Baburin
published in: Proceedings of the Steklov Institute of Mathematics
publication date: 2011-11-02T00:00:00Z
review text: The authors consider the problem of finding \(m\) edge-disjoint salesman tours. The problem is known also as the \(m\)-peripatetic salesman problem (\(m\)-PSP). The problem can be formulated as follows. A complete \(n\)-vertex undirected graph \(G= (V,E)\) is given, where \(V= \{1,\dots, n\}\) is the set of vertices and \(E= \{e= (v,u)\); \(v,u\in V\), \(v< u\}\) is the set of edges. A nonnegative weight function \(w: E\to R_+\) is defined on \(E\). It is required to find \(m\) edge-disjoint traveling salesman tours \(H_1,\dots, H_m\subset E\) such that the total weight of edges in the tours found is maximal. The authors propose an approximation algorithm for solving the \(m\)-PSP in a multidimensional Euclidean space and prove an upper bound for the number \(m\) of tours for which the algorithm gives an asymptotically optimal solution in polynomial time \(O(n^3)\).
reviewed by: Karel Zimmermann
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 5966604
zbMATH Keywords: maximum traveling salesman problem
zbMATH Keywords: edge-disjoint Hamiltonian circuits
zbMATH Keywords: asymptotic optimality
zbMATH Keywords: approximation algorithm
MaRDI profile type: Publication
cites work: Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2
cites work: An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
cites work: Job selection and sequencing on a single machine in a random environment
cites work: Lower bounds for symmetricK-peripatetic salesman problems
cites work: Q5187226
cites work: The traveling salesman problem and its variations
cites work: A heuristic approach to the overnight security service problem
full work available at URL: s0081543811020015
OpenAlex ID: W2015657372
description: scientific article; zbMATH DE number 5966604