E. Kh. Gimadi, A. M. Istomin, I. A. Rykov, O. Yu. Tsidulko, “Probabilistic analysis of an approximation algorithm for the $m$-peripatetic salesman problem on random instances unbounded from above”, Trudy Inst. Mat. i Mekh. UrO RAN, 20, no. 2, 2014, 88–98; Proc. Steklov Inst. Math. (Suppl.), 289, suppl. 1 (2015), 77

Trudy Instituta Matematiki i Mekhaniki UrO RAN

RUS ENG

JOURNALS PEOPLE ORGANISATIONS CONFERENCES SEMINARS VIDEO LIBRARY PACKAGE AMSBIB

JavaScript is disabled in your browser. Please switch it on to enable full functionality of the website

	General information
	Latest issue
	Archive
	Impact factor

	Search papers
	Search references

	RSS
	Latest issue
	Current issues
	Archive issues
	What is RSS

Trudy Inst. Mat. i Mekh. UrO RAN:
Year:
Volume:
Issue:
Page:
	Find

Personal entry:
Login:
Password:
	Save password
	Enter
	Forgotten password?
	Register

Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2014, Volume 20, Number 2, Pages 88–98 (Mi timm1061)

This article is cited in 2 scientific papers (total in 2 papers)

Probabilistic analysis of an approximation algorithm for the

m

$m$ -peripatetic salesman problem on random instances unbounded from above

E. Kh. Gimadi^ab, A. M. Istomin^ba, I. A. Rykov^ab, O. Yu. Tsidulko^ba

^a Novosibirsk State University
^b Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences

Full-text PDF (203 kB) Citations (2)

References:

PDF

HTML

Abstract: We present the probabilistic analysis of an approximation algorithm for the minimum-weight

m

$m$ -peripatetic salesman problem with different weight functions of their routes (Hamiltonian cycles). The time complexity of the algorithm is

O (m n^{2})

$O(mn^2)$ . We assume that the entries of the distance matrix are independent equally distributed random variables with values in an upper-unbounded domain

[a_{n}, \infty)

$[a_n,\infty)$ , where

a_{n} > 0

$a_n>0$ . The analysis is carried out for the example of truncated normal and exponential distributions. Estimates for the relative error and failure probability, as well as conditions for the asymptotic exactness of the algorithm, are found.

Keywords:

m

$m$ -peripatetic salesman problem, approximation algorithm, time complexity, asymptotic optimality, random instances, distribution function, truncated normal, exponential.

Received: 30.01.2014

English version:
Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2015, Volume 289, Issue 1, Pages 77–87
DOI: https://doi.org/10.1134/S0081543815050077

Bibliographic databases:

Document Type: Article

UDC: 519.16+519.85

Language: Russian

Citation: E. Kh. Gimadi, A. M. Istomin, I. A. Rykov, O. Yu. Tsidulko, “Probabilistic analysis of an approximation algorithm for the

m

$m$ -peripatetic salesman problem on random instances unbounded from above”, Trudy Inst. Mat. i Mekh. UrO RAN, 20, no. 2, 2014, 88–98; Proc. Steklov Inst. Math. (Suppl.), 289, suppl. 1 (2015), 77–87

Citation in format AMSBIB

\Bibitem{GimIstRyk14}

\by E.~Kh.~Gimadi, A.~M.~Istomin, I.~A.~Rykov, O.~Yu.~Tsidulko

\paper Probabilistic analysis of an approximation algorithm for the $m$-peripatetic salesman problem on random instances unbounded from above

\serial Trudy Inst. Mat. i Mekh. UrO RAN

\yr 2014

\vol 20

\issue 2

\pages 88--98

\mathnet{http://mi.mathnet.ru/timm1061}

\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3364142}

\elib{https://elibrary.ru/item.asp?id=21585627}

\transl

\jour Proc. Steklov Inst. Math. (Suppl.)

\yr 2015

\vol 289

\issue , suppl. 1

\pages 77--87

\crossref{https://doi.org/10.1134/S0081543815050077}

\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000356931500007}

\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84932616544}

Linking options:

https://www.mathnet.ru/eng/timm1061

https://www.mathnet.ru/eng/timm/v20/i2/p88

This publication is cited in the following 2 articles:

E. Kh. Gimadi, O. Yu. Tsidulko, “An asymptotically optimal algorithm for the $m$-peripatetic salesman problem on random inputs with discrete distribution”, J. Appl. Industr. Math., 11:3 (2017), 354–361
Edward Kh. Gimadi, Alexey M. Istomin, Oxana Yu. Tsidulko, Lecture Notes in Computer Science, 9869, Discrete Optimization and Operations Research, 2016, 136

Citing articles in Google Scholar: Russian citations, English citations
Related articles in Google Scholar: Russian articles, English articles

Trudy Instituta Matematiki i Mekhaniki UrO RAN

Statistics & downloads:
Abstract page:	394
Full-text PDF :	97
References:	72
First page:	11

Что такое QR-код?

Registration to the website

Logotypes