An asymptotically optimal algorithm for the m-Peripatetic Salesman Problem on random inputs with discrete distribution

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the m-Peripatetic Salesman Problem (m-PSP) on random inputs with discrete distribution function. In this paper we present a polynomial approximation algorithm which, under certain conditions, with high probability (w.h.p.) gives optimal solution for both the m-PSP on random inputs with identical weight functions and the m-PSP with different weight functions.

Original languageEnglish
Pages (from-to)354-361
Number of pages8
JournalJournal of Applied and Industrial Mathematics
Volume11
Issue number3
DOIs
Publication statusPublished - 1 Jul 2017

Keywords

  • asymptotically optimal algorithm
  • discrete distribution
  • m-Peripatetic Salesman Problem
  • random inputs

Fingerprint

Dive into the research topics of 'An asymptotically optimal algorithm for the m-Peripatetic Salesman Problem on random inputs with discrete distribution'. Together they form a unique fingerprint.

Cite this