Ссылки

DOI

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 + epsilon)-approximation algorithm for this classical problem proposed by O. Svensson and V. Traub in 2019.
Язык оригиналаАнглийский
Страницы (с-по)S140-S155
Число страниц16
ЖурналProceedings of the Steklov Institute of Mathematics
Том319
Номер выпускаS1
DOI
СостояниеОпубликовано - 1 дек. 2022

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

  • Mathematics (miscellaneous)

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

  • Математика, Прикладная
  • Математика

ID: 37085125