TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 15.03.2018

isti-logo

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

Back to the research colloquium site.

To top

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe