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.
Original languageEnglish
Pages (from-to)S140-S155
Number of pages16
JournalProceedings of the Steklov Institute of Mathematics
Volume319
Issue numberS1
DOIs
Publication statusPublished - 1 Dec 2022

    ASJC Scopus subject areas

  • Mathematics (miscellaneous)

    WoS ResearchAreas Categories

  • Mathematics, Applied
  • Mathematics

ID: 37085125