direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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.



Oxana Tsidulko
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras