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

A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP Научная публикация

Журнал

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

Вых. Данные

Год: 2019, Том: 13, Номер: 2, Страницы: 219-238 Страниц : 20 DOI: 10.1134/S1990478919020042

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

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, pr. Akad. Koptyuga 4, Novosibirsk, 630090, Russian Federation
2	Novosibirsk State University, ul. Pirogova 1, Novosibirsk, 630090, Russian Federation

We present a first polynomial algorithm with guaranteed approximation ratio for the asymmetric maximization version of the asymmetric 3-Peripatetic Salesman Problem (3-APSP). This problem consists in finding the three edge-disjoint Hamiltonian circuits of maximal total weight in a complete weighted digraph. We prove that the algorithm has guaranteed approximation ratio 3/5 and cubic running-time. © 2019, Pleiades Publishing, Ltd.

Glebov A.N. , Toktokhoeva S.G.
A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP
Journal of Applied and Industrial Mathematics. 2019. V.13. N2. P.219-238. DOI: 10.1134/S1990478919020042 Scopus OpenAlex

Глебов А.Н. , Токтохоева С.Г.
Полиномиальный 3/5-приближённый алгоритм для несимметричной задачи о трёх коммивояжёрах на максимум
Дискретный анализ и исследование операций. 2019. Т.26. №2. С.30-59.

Scopus:	2-s2.0-85067404465
OpenAlex:	W2952489944

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