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

DOI10.1134/S0081543811020015MaRDI QIDQ643801zbMATH OpenOpenAlexFDO

Authors Eh. 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)

Recommendations

• Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space
• Asymptotically optimal algorithms for geometric MAX TSP and MAX \(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
• The Undirected m-Peripatetic Salesman Problem: Polyhedral Results and New Algorithms

Cites work

• scientific article; zbMATH DE number 3895002 (Why is no real title available?)
• A heuristic approach to the overnight security service problem
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• 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
• Lower bounds for symmetricK-peripatetic salesman problems
• The traveling salesman problem and its variations

Cited in

(20)

• The Undirected m-Peripatetic Salesman Problem: Polyhedral Results and New Algorithms
• Approximation algorithms for 2-PSP-2W-max and 2-CC-2W-max
• Heuristiques pour le Problème du Vendeurm-Péripatétique
• scientific article; zbMATH DE number 4068645 (Why is no real title available?)
• Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph
• On asymptotically optimal approach to the m-Peripatetic Salesman problem on random inputs
• An asymptotically optimal algorithm for the \(m\)-peripatetic salesman problem on random inputs with discrete distribution
• A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph
• Efficient algorithms with performance guarantees for some problems of finding several cliques in a complete undirected weighted graph
• Approximability of the problem about a minimum-weight cycle cover of a graph
• Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space
• The undirected \(m\)-capacitated peripatetic salesman problem
• A polynomial algorithm with asymptotic ratio \(2/3\) for the asymmetric maximization version of the \(m\)-PSP
• An \(O(mn^ 2)\) algorithm for the maximin problem in \(E^ 2\)
• A polynomial 3/5-approximate algorithm for the asymmetric maximization version of the 3-PSP
• Asymptotically optimal algorithms for geometric MAX TSP and MAX \(m\)-PSP
• Probabilistic analysis of an approximation algorithm for the m-peripatetic salesman problem on random instances unbounded from above
• scientific article; zbMATH DE number 1985657 (Why is no real title available?)
• Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph
• On asymptotically optimal solvability of max \(m\)-\(k\)-cycles cover problem in a normed space

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q643801)