Approximation algorithms for the maximum m-peripatetic salesman problem

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

Аннотация

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.

Язык оригиналаанглийский
Название основной публикации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
Страницы304-312
Число страниц9
ISBN (печатное издание)9783319730127
DOI
СостояниеОпубликовано - 1 янв 2018
Событие6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017 - Moscow, Российская Федерация
Продолжительность: 27 июл 201729 июл 2017

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том10716 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017
СтранаРоссийская Федерация
ГородMoscow
Период27.07.201729.07.2017

Fingerprint Подробные сведения о темах исследования «Approximation algorithms for the maximum m-peripatetic salesman problem». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    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