Standard

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

в: Journal of Applied and Industrial Mathematics, Том 11, № 3, 01.07.2017, стр. 354-361.

Результаты исследований: Научные публикации в периодических изданияхстатьяРецензирование

Harvard

APA

Vancouver

Gimadi EK, Tsidulko OY. An asymptotically optimal algorithm for the m-Peripatetic Salesman Problem on random inputs with discrete distribution. Journal of Applied and Industrial Mathematics. 2017 июль 1;11(3):354-361. doi: 10.1134/S1990478917030061

Author

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

N1 - Publisher Copyright: © 2017, Pleiades Publishing, Ltd.

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