Please use this identifier to cite or link to this item:
http://elar.urfu.ru/handle/10995/127431
Title: | FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM |
Authors: | Rizhenko, K. Neznakhina, K. Khachay, M. |
Issue Date: | 2023 |
Citation: | Rizhenko K. FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM / K. Rizhenko, K. Neznakhina, M. Khachay. — Text : electronic // Ural Mathematical Journal. — 2023. — Volume 9. — № 1. — P. 135-146. |
Abstract: | We develop the first fixed-ratio approximation algorithm for the well-known Prize-Collecting Asymmetric Traveling Salesman Problem, which has numerous valuable applications in operations research. An instance of this problem is given by a complete node- and edge-weighted digraph G. Each node of the graph G can either be visited by the resulting route or skipped, for some penalty, while the arcs of G are weighted by non-negative transportation costs that fulfill the triangle inequality constraint. The goal is to find a closed walk that minimizes the total transportation costs augmented by the accumulated penalties. We show that an arbitrary α-approximation algorithm for the Asymmetric Traveling Salesman Problem induces an (α + 1)-approximation for the problem in question. In particular, using the recent (22 + ε)-approximation algorithm of V. Traub and J. Vygen that improves the seminal result of O. Svensson, J. Tarnavski, and L. Végh, we obtain (23 + ε)-approximate solutions for the problem. |
Keywords: | PRIZE-COLLECTING TRAVELING SALESMAN PROBLEM TRIANGLE INEQUALITY APPROXIMATION ALGORITHM FIXED APPROXIMATION RATIO |
URI: | http://elar.urfu.ru/handle/10995/127431 |
Access: | Creative Commons Attribution License |
License text: | https://creativecommons.org/licenses/by/4.0/ |
RSCI ID: | 54265312 |
ISSN: | 2414-3952 |
DOI: | 10.15826/umj.2023.1.012 |
Origin: | Ural Mathematical Journal. 2023. Volume 9. № 1 |
Appears in Collections: | Ural Mathematical Journal |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
umj_2023_9_1_013.pdf | 247,57 kB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License