On the asymptotically optimal approaches to the m-Peripatetic Salesman Problem on random inputs
Oxana Tsidulko (Sobolev Institute of Mathematics, Novosibirsk State University)
The m-Peripatetic Salesman Problem (m-PSP) is a natural generalization of the well-known Traveling Salesman Problem (TSP). Given a complete n-vertex edge-weighted graph, the goal is to determine m edge-disjoint Hamiltonian cycles of minimum total weight. The m-PSP is strongly NP-hard. The presentation discusses two simple polynomial approximation algorithms for the m-PSP. We show that if m=o(n), then for a certain classes of random inputs these algorithms give asymptotically optimal solutions for the problem, meaning that with high probability the relative errors tend to zero as the number of the vertices n tends to infinity.
Back to the research colloquium site.