Khachay M. Y. Constant-Factor Approximation Algorithms for a Series of Combinatorial Routing Problems Based on the Reduction to the Asymmetric Traveling Salesman Problem. Большая российская энциклопедия

Заглавие:: Constant-Factor Approximation Algorithms for a Series of Combinatorial Routing Problems Based on the Reduction to the Asymmetric Traveling Salesman Problem
Автор:: Khachay M. Y.
Аннотация:: For the first time, algorithms with constant performance guarantees are substantiated for a series of asymmetric routing problems of combinatorial optimization: the Steiner cycle problem (SCP), the generalized traveling salesman problem (GTSP), the capacitated vehicle routing problem with unsplittable customer demands (CVRP-UCD), and the prize collecting traveling salesman problem (PCTSP). The presented results are united by the property that they all rely on polynomial cost-preserving reduction to appropriate instances of the asymmetric traveling salesman problem (ATSP) and on the 22 ε -approximation algorithm for this classical problem proposed by O. Svensson and V. Traub in 2019.
Язык текста:: Английский
Сведения об источнике:: Proceedings of the Steklov Institute of Mathematics. – 2022. – Vol. 319, suppl. 1. – P. S140–S155.