Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://elar.urfu.ru/handle/10995/127431
Название: | FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM |
Авторы: | Rizhenko, K. Neznakhina, K. Khachay, M. |
Дата публикации: | 2023 |
Библиографическое описание: | 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. |
Аннотация: | 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. |
Ключевые слова: | PRIZE-COLLECTING TRAVELING SALESMAN PROBLEM TRIANGLE INEQUALITY APPROXIMATION ALGORITHM FIXED APPROXIMATION RATIO |
URI: | http://elar.urfu.ru/handle/10995/127431 |
Условия доступа: | Creative Commons Attribution License |
Текст лицензии: | https://creativecommons.org/licenses/by/4.0/ |
Идентификатор РИНЦ: | 54265312 |
ISSN: | 2414-3952 |
DOI: | 10.15826/umj.2023.1.012 |
Источники: | Ural Mathematical Journal. 2023. Volume 9. № 1 |
Располагается в коллекциях: | Ural Mathematical Journal |
Файлы этого ресурса:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
umj_2023_9_1_013.pdf | 247,57 kB | Adobe PDF | Просмотреть/Открыть |
Лицензия на ресурс: Лицензия Creative Commons