An algorithm with approximation ratio 5/6 for the metric maximum m-PSP

DOI10.1007/978-3-319-44914-2_13zbMATH Open1392.90096OpenAlexW2557967660MaRDI QIDQ3133209FDOQ3133209

Authors A. V. Gordeeva, A. N. Glebov

Publication date 13 February 2018

Published in Discrete Optimization and Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-44914-2_13

zbMATH Keywords

approximation algorithmmetric TSPmaximization version of the \(m\)-PSPmaximization version of the TSPmetric \(m\)-PSP

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Algorithms – ESA 2005
• Improved approximation algorithms for metric MaxTSP
• A \(\frac78\)-approximation algorithm for metric Max TSP
• A polynomial algorithm with asymptotic ratio \(2/3\) for the asymmetric maximization version of the \(m\)-PSP
• Improved deterministic approximation algorithms for max TSP

Cited in

(4)

• A polynomial 3/5-approximate algorithm for the asymmetric maximization version of the 3-PSP
• An asymptotically optimal algorithm for the \(m\)-peripatetic salesman problem on random inputs with discrete distribution
• A polynomial algorithm with asymptotic ratio \(2/3\) for the asymmetric maximization version of the \(m\)-PSP
• Approximation algorithms for 2-PSP-2W-max and 2-CC-2W-max

This page was built for publication: An algorithm with approximation ratio 5/6 for the metric maximum \(m\)-PSP

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