In this paper, the first fixed-ratio approximation algorithms are proposed for the series of asymmetric settings of the 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 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 more deep extension of their approach.
Translated title of the contributionAPPROXIMATION ALGORITHMS WITH CONSTANT FACTORS FOR A SERIES OF ASYMMETRIC ROUTING PROBLEMS
Original languageRussian
Pages (from-to)89-97
Number of pages9
JournalДоклады Российской академии наук. Математика, информатика, процессы управления
Volume514
Issue number1
DOIs
Publication statusPublished - 2023

    Level of Research Output

  • Russian Science Citation Index

ID: 51707300