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

Standard

An asymptotically optimal algorithm for the m-Peripatetic Salesman Problem on random inputs with discrete distribution. / Gimadi, E. Kh ; Tsidulko, O. Yu.

In: Journal of Applied and Industrial Mathematics, Vol. 11, No. 3, 01.07.2017, p. 354-361.

Research output: Contribution to journal › Article › peer-review

BibTeX

@article{ebbc7f53bf4546bd98fa448d975ce7d5,

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

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.",

keywords = "asymptotically optimal algorithm, discrete distribution, m-Peripatetic Salesman Problem, random inputs",

author = "Gimadi, {E. Kh} and Tsidulko, {O. Yu}",

note = "Publisher Copyright: {\textcopyright} 2017, Pleiades Publishing, Ltd.",

year = "2017",

month = jul,

day = "1",

doi = "10.1134/S1990478917030061",

language = "English",

volume = "11",

pages = "354--361",

journal = "Journal of Applied and Industrial Mathematics",

issn = "1990-4789",

publisher = "Maik Nauka-Interperiodica Publishing",

number = "3",

}

RIS

TY - JOUR

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

AU - Gimadi, E. Kh

AU - Tsidulko, O. Yu

PY - 2017/7/1

Y1 - 2017/7/1

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

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

KW - asymptotically optimal algorithm

KW - discrete distribution

KW - m-Peripatetic Salesman Problem

KW - random inputs

UR - http://www.scopus.com/inward/record.url?scp=85028554513&partnerID=8YFLogxK

U2 - 10.1134/S1990478917030061

DO - 10.1134/S1990478917030061

M3 - Article

AN - SCOPUS:85028554513

VL - 11

SP - 354

EP - 361

JO - Journal of Applied and Industrial Mathematics

JF - Journal of Applied and Industrial Mathematics

SN - 1990-4789

IS - 3

ER -

ID: 9918548