The Prize-Collecting Traveling Salesman Problem is an extension of the classic Traveling Salesman Problem, where each node of the given graph can be skipped for some known penalty. The goal is to construct a closed walk minimizing the total transportation costs and accumulated penalties. This problem has numerous applications in operations research, including sustainable production, supply chains, and drone routing. In this paper, we propose the first approximation algorithm with constant ratio for the asymmetric version of the problem on a complete weighted digraph, where the transportation costs fulfill the triangle inequality. Employing an arbitrary α -approximation algorithm for the Asymmetric Traveling Salesman Problem (ATSP) as a building block, our algorithm establishes an (α+ 2 ) -approximation for the Prize-Collecting Asymmetric Traveling Salesman Problem. In particular, using the seminal recent Swensson-Traub (22 + ε) -approximation algorithm for the ATSP, we obtain (24 + ε) -approximate solutions for our problem.
Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Subtitle of host publicationBook Series
PublisherSpringer
Pages81-90
Number of pages10
ISBN (Electronic)978-3-031-22543-7
ISBN (Print)978-303122542-0
DOIs
Publication statusPublished - 3 Jan 2023

Publication series

NameOptimization and Applications
Volume13781
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

    ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

    WoS ResearchAreas Categories

  • Computer Science, Software Engineering
  • Operations Research & Management Science
  • Mathematics, Applied

ID: 35508811