Standard

Prize-Collecting Asymmetric Traveling Salesman Problem Admits Polynomial Time Approximation Within a Constant Ratio: book chapter. / Khachay, Michael; Neznakhina, Katherine; Rizhenko, Ksenia.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Book Series. Springer, 2023. стр. 81-90 Chapter 6 (Optimization and Applications; Том 13781).

Результаты исследований: Глава в книге, отчете, сборнике статей › Глава › Рецензирование

Harvard

Khachay, M, Neznakhina, K & Rizhenko, K 2023, Prize-Collecting Asymmetric Traveling Salesman Problem Admits Polynomial Time Approximation Within a Constant Ratio: book chapter. в Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Book Series., Chapter 6, Optimization and Applications, Том. 13781, Springer, стр. 81-90. https://doi.org/10.1007/978-3-031-22543-7_6

APA

Khachay, M., Neznakhina, K., & Rizhenko, K. (2023). Prize-Collecting Asymmetric Traveling Salesman Problem Admits Polynomial Time Approximation Within a Constant Ratio: book chapter. в Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Book Series (стр. 81-90). [Chapter 6] (Optimization and Applications; Том 13781). Springer. https://doi.org/10.1007/978-3-031-22543-7_6

Vancouver

Khachay M, Neznakhina K, Rizhenko K. Prize-Collecting Asymmetric Traveling Salesman Problem Admits Polynomial Time Approximation Within a Constant Ratio: book chapter. в Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Book Series. Springer. 2023. стр. 81-90. Chapter 6. (Optimization and Applications). doi: 10.1007/978-3-031-22543-7_6

Author

Khachay, Michael ; Neznakhina, Katherine ; Rizhenko, Ksenia. / Prize-Collecting Asymmetric Traveling Salesman Problem Admits Polynomial Time Approximation Within a Constant Ratio : book chapter. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Book Series. Springer, 2023. стр. 81-90 (Optimization and Applications).

BibTeX

@inbook{d5e421319233438a9afde3152da440d5,
title = "Prize-Collecting Asymmetric Traveling Salesman Problem Admits Polynomial Time Approximation Within a Constant Ratio: book chapter",
abstract = "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. ",
author = "Michael Khachay and Katherine Neznakhina and Ksenia Rizhenko",
note = "This research was carried out under the financial support of the Russian Science Foundation, grant no. 22-21-00672, https://rscf.ru/project/22-21-00672/.",
year = "2023",
month = jan,
day = "3",
doi = "10.1007/978-3-031-22543-7_6",
language = "English",
isbn = "978-303122542-0",
series = "Optimization and Applications",
publisher = "Springer",
pages = "81--90",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
address = "Germany",

}

RIS

TY - CHAP

T1 - Prize-Collecting Asymmetric Traveling Salesman Problem Admits Polynomial Time Approximation Within a Constant Ratio

T2 - book chapter

AU - Khachay, Michael

AU - Neznakhina, Katherine

AU - Rizhenko, Ksenia

N1 - This research was carried out under the financial support of the Russian Science Foundation, grant no. 22-21-00672, https://rscf.ru/project/22-21-00672/.

PY - 2023/1/3

Y1 - 2023/1/3

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85148694799&partnerID=8YFLogxK

UR - https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=tsmetrics&SrcApp=tsm_test&DestApp=WOS_CPL&DestLinkType=FullRecord&KeyUT=000968310600006

U2 - 10.1007/978-3-031-22543-7_6

DO - 10.1007/978-3-031-22543-7_6

M3 - Chapter

SN - 978-303122542-0

T3 - Optimization and Applications

SP - 81

EP - 90

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

PB - Springer

ER -

ID: 35508811