An Algorithm with Approximation Ratio 5/6 for the Metric Maximum m-PSP

摘要

We present a polynomial algorithm with guaranteed approximation ratio 5/6 for the metric maximization version of the m-PSP with identical weight functions. This result extends the well-known algorithm by Kostochka and Serdyukov for the metric TSP (1985) to the case of several Hamiltonian cycles and improves the approximation ratio of the algorithm by Gordeeva (2010) for the metric 2-PSP.