A Polynomial Algorithm with Asymptotic Ratio 2/3 for the Asymmetric Maximization Version of the m-PSP | Sciact - Система учета научной деятельности ИМ СО РАН

A Polynomial Algorithm with Asymptotic Ratio 2/3 for the Asymmetric Maximization Version of the m-PSP Научная публикация

Журнал

Journal of Applied and Industrial Mathematics
ISSN: 1990-4789 , E-ISSN: 1990-4797

Вых. Данные

Год: 2020, Том: 14, Номер: 3, Страницы: 456-469 Страниц : 14 DOI: 10.1134/S1990478920030059

Ключевые слова

approximation algorithm; guaranteed approximation ratio; Hamiltonian cycle; m-Peripatetic Salesman Problem; Traveling Salesman Problem

Авторы

Glebov A.N. ^1,2 , Toktokhoeva S.G. ²

Организации

1	Sobolev Institute of Mathematics, Novosibirsk, 630090, Russian Federation
2	Novosibirsk State University, Novosibirsk, 630090, Russian Federation

Abstract: In 2005, Kaplan et al. presented a polynomial-time algorithm with guaranteedapproximation ratio 2/3 for themaximization version of the asymmetric TSP. In 2014, Glebov, Skretneva, and Zambalaevaconstructed a similar algorithm with approximation ratio 2/3 and cubic runtime for the maximization version ofthe asymmetric 2-PSP (2-APSP-max), where it is required to find twoedge-disjoint Hamiltonian cycles of maximum total weight in a complete directed weighted graph.The goal of this paper is to construct a similar algorithm for the more general m-APSP-max in the asymmetric case and justify anapproximation ratio for this algorithm that tends to 2/3 as n grows and theruntime complexity estimate O(mn3). © 2020, Pleiades Publishing, Ltd.

Glebov A.N. , Toktokhoeva S.G.
A Polynomial Algorithm with Asymptotic Ratio 2/3 for the Asymmetric Maximization Version of the m-PSP
Journal of Applied and Industrial Mathematics. 2020. V.14. N3. P.456-469. DOI: 10.1134/S1990478920030059 Scopus OpenAlex

Глебов А.Н. , Токтохоева С.Г.
Полиномиальный алгоритм с асимптотической оценкой точности 2/3 для несимметричной задачи об m коммивояжёрах на максимум
Дискретный анализ и исследование операций. 2020. Т.27. №3. С.28–52.

Scopus:	2-s2.0-85094634807
OpenAlex:	W3095646251

БД	Цитирований
Scopus	1