A Polynomial Algorithm with Asymptotic Ratio 2/3 for the Asymmetric Maximization Version of the m-PSP

A. N. Glebov, S. G. Toktokhoeva

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование

Аннотация

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).

Язык оригиналаанглийский
Страницы (с-по)456-469
Число страниц14
ЖурналJournal of Applied and Industrial Mathematics
Том14
Номер выпуска3
DOI
СостояниеОпубликовано - 1 авг 2020

Fingerprint Подробные сведения о темах исследования «A Polynomial Algorithm with Asymptotic Ratio 2/3 for the Asymmetric Maximization Version of the m-PSP». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать