### Page Content

### to Navigation

# 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.

Date | Speaker | Location | Language |
---|---|---|---|

15.03.2018 16:15 | Oxana Tsidulko | TEL 512 | English |