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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cited In (4)

• A polynomial algorithm with asymptotic ratio $2/3$ for the asymmetric maximization version of the $m$-PSP
• A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP
• Approximation algorithms for 2-PSP-2W-max and 2-CC-2W-max
• An asymptotically optimal algorithm for the m-Peripatetic Salesman Problem on random inputs with discrete distribution

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)