Ссылки

DOI

Abstract: In this paper, the first fixed-ratio approximation algorithms are proposed for a series of asymmetric settings of well-known combinatorial routing problems. Among them are the Steiner cycle problem, the prize-collecting traveling salesman problem, the minimum cost cycle cover problem by a bounded number of cycles, etc. Almost all of the proposed algorithms rely on original reductions of the considered problems to auxiliary instances of the asymmetric traveling salesman problem and employ the breakthrough approximation results for this problem obtained recently by O. Svensson, J. Tarnawski, L. Végh, V. Traub, and J. Vygen. On the other hand, approximation of the cycle cover problem was proved by applying a deeper extension of their approach. © Pleiades Publishing, Ltd. 2023. ISSN 1064-5624, Doklady Mathematics, 2023, Vol. 108, No. 3, pp. 499–505. Pleiades Publishing, Ltd., 2023. Russian Text The Author(s), 2023, published in Doklady Rossiiskoi Akademii Nauk. Matematika, Informatika, Protsessy Upravleniya, 2023, Vol. 514, pp. 89–97.
Язык оригиналаАнглийский
Страницы (с-по)499-505
Число страниц7
ЖурналDoklady Mathematics
Том108
Номер выпуска3
DOI
СостояниеОпубликовано - 2023

    Предметные области ASJC Scopus

  • Математика в целом

    Предметные области WoS

  • Математика

ID: 54317257