On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space

DOI10.1134/S0081543811020015zbMath1230.65065OpenAlexW2015657372MaRDI QIDQ643801

E. Kh. Gimadi, Alexei E. Baburin

Publication date: 2 November 2011

Published in: Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s0081543811020015

zbMATH Keywords

approximation algorithmasymptotic optimalitymaximum traveling salesman problemedge-disjoint Hamiltonian circuits

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05)

Related Items (10)

Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph ⋮ A polynomial algorithm with asymptotic ratio $2/3$ for the asymmetric maximization version of the $m$-PSP ⋮ An asymptotically optimal algorithm for the m-Peripatetic Salesman Problem on random inputs with discrete distribution ⋮ Probabilistic analysis of an approximation algorithm for the \(m\)-peripatetic salesman problem on random instances unbounded from above ⋮ Efficient algorithms with performance guarantees for some problems of finding several cliques in a complete undirected weighted graph ⋮ A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph ⋮ Approximability of the problem about a minimum-weight cycle cover of a graph ⋮ Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph ⋮ The undirected \(m\)-capacitated peripatetic salesman problem ⋮ A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP

Cites Work

• Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2
• Job selection and sequencing on a single machine in a random environment
• The traveling salesman problem and its variations
• A heuristic approach to the overnight security service problem
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Lower bounds for symmetricK-peripatetic salesman problems
• Unnamed Item

This page was built for publication: On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space