Ссылки

DOI

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.
Язык оригиналаАнглийский
Название основной публикацииLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Подзаголовок основной публикацииBook Series
ИздательSpringer
Страницы81-90
Число страниц10
ISBN (электронное издание)978-3-031-22543-7
ISBN (печатное издание)978-303122542-0
DOI
СостояниеОпубликовано - 3 янв. 2023

Серия публикаций

НазваниеOptimization and Applications
Том13781
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

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

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Компьютерные науки, Разработка программного обеспечения
  • Управление и менеджмент
  • Математика, Прикладная

ID: 35508811