Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review
Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review
}
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