Standard
Approximation algorithms for the maximum m-peripatetic salesman problem. / Gimadi, Edward Kh; Tsidulko, Oxana Yu.
Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers. ред. / WMP VanDerAalst; DI Ignatov; M Khachay; SO Kuznetsov; Lempitsky; IA Lomazova; N Loukachevitch; A Napoli; A Panchenko; PM Pardalos; AV Savchenko; S Wasserman. Springer-Verlag GmbH and Co. KG, 2018. стр. 304-312 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 10716 LNCS).
Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Harvard
Gimadi, EK & Tsidulko, OY 2018,
Approximation algorithms for the maximum m-peripatetic salesman problem. в WMP VanDerAalst, DI Ignatov, M Khachay, SO Kuznetsov, Lempitsky, IA Lomazova, N Loukachevitch, A Napoli, A Panchenko, PM Pardalos, AV Savchenko & S Wasserman (ред.),
Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Том. 10716 LNCS, Springer-Verlag GmbH and Co. KG, стр. 304-312, 6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017, Moscow, Российская Федерация,
27.07.2017.
https://doi.org/10.1007/978-3-319-73013-4_28
APA
Gimadi, E. K., & Tsidulko, O. Y. (2018).
Approximation algorithms for the maximum m-peripatetic salesman problem. в WMP. VanDerAalst, DI. Ignatov, M. Khachay, SO. Kuznetsov, Lempitsky, IA. Lomazova, N. Loukachevitch, A. Napoli, A. Panchenko, PM. Pardalos, AV. Savchenko, & S. Wasserman (Ред.),
Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers (стр. 304-312). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 10716 LNCS). Springer-Verlag GmbH and Co. KG.
https://doi.org/10.1007/978-3-319-73013-4_28
Vancouver
Gimadi EK, Tsidulko OY.
Approximation algorithms for the maximum m-peripatetic salesman problem. в VanDerAalst WMP, Ignatov DI, Khachay M, Kuznetsov SO, Lempitsky, Lomazova IA, Loukachevitch N, Napoli A, Panchenko A, Pardalos PM, Savchenko AV, Wasserman S, Редакторы, Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers. Springer-Verlag GmbH and Co. KG. 2018. стр. 304-312. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-73013-4_28
Author
Gimadi, Edward Kh ; Tsidulko, Oxana Yu. /
Approximation algorithms for the maximum m-peripatetic salesman problem. Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers. Редактор / WMP VanDerAalst ; DI Ignatov ; M Khachay ; SO Kuznetsov ; Lempitsky ; IA Lomazova ; N Loukachevitch ; A Napoli ; A Panchenko ; PM Pardalos ; AV Savchenko ; S Wasserman. Springer-Verlag GmbH and Co. KG, 2018. стр. 304-312 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{f1ddfd152b974729ba551cefc61a2f67,
title = "Approximation algorithms for the maximum m-peripatetic salesman problem",
abstract = "We consider the maximum m-Peripatetic Salesman Problem (MAX m-PSP), which is a natural generalization of the classic Traveling Salesman Problem. The problem is strongly NP-hard. In this paper we propose two polynomial approximation algorithms for the MAX m-PSP with different and identical weight functions, correspondingly. We prove that for random inputs uniformly distributed on the interval [a, b] these algorithms are asymptotically optimal for m= o(n). This means that with high probability their relative errors tend to zero as the number n of the vertices of the graph tends to infinity. The results remain true for the distributions of inputs that minorize the uniform distribution.",
keywords = "Edge-disjoint Hamiltonian cycles, Maximum m-Peripatetic salesman problem, Time complexity, Maximum m-Peripatetic Salesman Problem, CYCLES",
author = "Gimadi, {Edward Kh} and Tsidulko, {Oxana Yu}",
year = "2018",
month = jan,
day = "1",
doi = "10.1007/978-3-319-73013-4_28",
language = "English",
isbn = "9783319730127",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag GmbH and Co. KG",
pages = "304--312",
editor = "WMP VanDerAalst and DI Ignatov and M Khachay and SO Kuznetsov and Lempitsky and IA Lomazova and N Loukachevitch and A Napoli and A Panchenko and PM Pardalos and AV Savchenko and S Wasserman",
booktitle = "Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers",
address = "Germany",
note = "6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017 ; Conference date: 27-07-2017 Through 29-07-2017",
}
RIS
TY - GEN
T1 - Approximation algorithms for the maximum m-peripatetic salesman problem
AU - Gimadi, Edward Kh
AU - Tsidulko, Oxana Yu
PY - 2018/1/1
Y1 - 2018/1/1
N2 - We consider the maximum m-Peripatetic Salesman Problem (MAX m-PSP), which is a natural generalization of the classic Traveling Salesman Problem. The problem is strongly NP-hard. In this paper we propose two polynomial approximation algorithms for the MAX m-PSP with different and identical weight functions, correspondingly. We prove that for random inputs uniformly distributed on the interval [a, b] these algorithms are asymptotically optimal for m= o(n). This means that with high probability their relative errors tend to zero as the number n of the vertices of the graph tends to infinity. The results remain true for the distributions of inputs that minorize the uniform distribution.
AB - We consider the maximum m-Peripatetic Salesman Problem (MAX m-PSP), which is a natural generalization of the classic Traveling Salesman Problem. The problem is strongly NP-hard. In this paper we propose two polynomial approximation algorithms for the MAX m-PSP with different and identical weight functions, correspondingly. We prove that for random inputs uniformly distributed on the interval [a, b] these algorithms are asymptotically optimal for m= o(n). This means that with high probability their relative errors tend to zero as the number n of the vertices of the graph tends to infinity. The results remain true for the distributions of inputs that minorize the uniform distribution.
KW - Edge-disjoint Hamiltonian cycles
KW - Maximum m-Peripatetic salesman problem
KW - Time complexity
KW - Maximum m-Peripatetic Salesman Problem
KW - CYCLES
UR - http://www.scopus.com/inward/record.url?scp=85039436251&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-73013-4_28
DO - 10.1007/978-3-319-73013-4_28
M3 - Conference contribution
AN - SCOPUS:85039436251
SN - 9783319730127
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 304
EP - 312
BT - Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers
A2 - VanDerAalst, WMP
A2 - Ignatov, DI
A2 - Khachay, M
A2 - Kuznetsov, SO
A2 - Lempitsky, null
A2 - Lomazova, IA
A2 - Loukachevitch, N
A2 - Napoli, A
A2 - Panchenko, A
A2 - Pardalos, PM
A2 - Savchenko, AV
A2 - Wasserman, S
PB - Springer-Verlag GmbH and Co. KG
T2 - 6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017
Y2 - 27 July 2017 through 29 July 2017
ER -
