APPROXIMATION ALGORITHMS WITH CONSTANT FACTORS FOR A SERIES OF ASYMMETRIC ROUTING PROBLEMS

E. D. Neznakhina; Незнахина Е. Д.; Yu. Yu. Ogorodnikov; Огородников Ю. Ю.; K. V. Rizhenko; Рыженко К. В.; M. Yu. Khachay; Хачай М. Ю.

doi:10.31857/S268695432360218X

APPROXIMATION ALGORITHMS WITH CONSTANT FACTORS FOR A SERIES OF ASYMMETRIC ROUTING PROBLEMS

Авторлар: Neznakhina E.¹^,2, Ogorodnikov Y.¹^,2, Rizhenko K.¹, Khachay M.¹
Мекемелер:
1. N.N. Krasovskii Institute of Mathematics and Mechanics
2. Ural federal university
Шығарылым: Том 514, № 1 (2023)
Беттер: 89-97
Бөлім: МАТЕМАТИКА
URL: https://journals.rcsi.science/2686-9543/article/view/247096
DOI: https://doi.org/10.31857/S268695432360218X
EDN: https://elibrary.ru/CYSMDZ
ID: 247096

Дәйексөз келтіру

Толық мәтін

Ашық рұқсат
Рұқсат жабық

Рұқсат берілді
Рұқсат жабық

Тек жазылушылар үшін

Аннотация
Авторлар туралы
Әдебиет тізімі
Қосымша файлдар
Статистика

Аннотация

In this paper, the first fixed-ratio approximation algorithms are proposed for the series of asymmetric settings of the well-known combinatorial routing problems. Among them are the Steiner cycle problem, the prize-collecting traveling salesman problem, the minimum cost cycle cover problem by a bounded number of cycles, etc. Almost all the proposed algorithms rely on original reductions of the considered problems to auxiliary instances of the Asymmetric Traveling Salesman Problem and employ the breakthrough approximation results for this problem obtained recently by O. Svensson, J. Tarnawski, L. Végh, V. Traub and J. Vygen. On the other hand, approximation of the cycle cover problem was proved by more deep extension of their approach.

Негізгі сөздер

asymmetric traveling salesman problem, approximation algorithm, constant ratio, Steiner cycle problem, Vehicle Routing Problem, Cycle Cover Problem

Әдебиет тізімі

Gutin G., Punnen A.P. The Traveling Salesman Problem and Its Variations. Springer US, Boston, MA, 2007.
Toth P., Vigo D. Vehicle Routing. Problems, Methods, and Applications. SIAM, Philadelphia, 2014.
Desrosiers J. and Lübbecke M.E. Branch-Price-and-Cut Algorithms. In Wiley Encyclopedia of Operations Research and Management Science (eds. J.J. Cochran, L.A. Cox, P. Keskinocak, J.P. Kharoufeh and J.C. Smith). Wiley and Sons, NJ. 2015.
Gendreau M., Potvin J.-Y. Handbook of Metaheuristics. Springer. 2019.
Vazirani V. Approximation algorithms. Springer. Berlin. 2003.
Williamson D.P., Shmoys D.B. The Design of Approximation Algorithms. New York, USA, 2011.
Christofides N. Worst-case analysis of a new heuristic for the Travelling Salesman Problem // Technical Report 388. Graduate School of Industrial Administration. Carnegie-Mellon University. 1976.
Сердюков А.И. О некоторых экстремальных обходах в графах // Управляемые системы. 1978. Т. 17. С. 76–79.
Haimovich M., Rinnooy Kan A.H.G. Bounds and Heuristics for Capacitated Routing Problems // Mathematics of Operations Research. 1985. V. 10. № 4. P. 527–542.
Asadpour A., Goemans M.X., Mądry A., Gharan S.O., Saberi A. An -approximation algorithm for the asymmetric traveling salesman problem // Operations Research. 2017. V. 65. № 4. P. 1043–1061.
Svensson O., Tarnawski J., Vegh L.A. A constant-factor approximation algorithm for the Asymmetric Traveling Salesman Problem // J. ACM. 2020. V. 67. № 6. P. 1–53.
Traub V., Vygen J. An improved approximation algorithm for the Asymmetric Traveling Salesman Problem // SIAM Journal on Computing. 2022. V. 51. № 1. P. 139–173.
Khachay M., Neznakhina E., Ryzhenko K. Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the Asymmetric Traveling Salesman Problem // Proc. Steklov Inst. Math. 2022. V. 319. № 1. P. S140–S155.
Rizhenko K., Neznakhina K., Khachay M. Fixed ratio polynomial time approximation algorithm for the Prize-Collecting Asymmetric Traveling Salesman Problem // Ural Math. Journal. 2023. V. 9. № 1. P. 135–146.
Хачай М.Ю., Незнахина Е.Д., Рыженко К.В. Полиномиальная аппроксимируемость асимметричной задачи о покрытии графа ограниченным числом циклов // Труды Института математики и механики УрО РАН. 2023. Т. 29. № 3. С. 261–273.
van Bevern R., Hartung S., Nichterlein A., Sorge M. Constant-factor approximations for capacitated arc routing without triangle inequality // Operations Research Letters. 2014. V. 42. № 4. P. 290–292.
Papadimitriou C. Euclidean TSP is NP-complete // Theoret. Comput. Sci. 1977. V. 4. P. 237–244.
Bienstock D., Goemans M.X., Simchi-Levi D., Williamson D. A note on the Prize-Collecting Traveling Salesman Problem // Math. Program. 1993. V. 59. P. 413–420.
Khachay M., Neznakhina K. Approximability of the Minimum-Weight -Size Cycle Cover Problem // J. of Global Optimization. 2016. V. 66. № 1. P. 65–82.
VRP-REP: the vehicle routing problem repository. http://www.vrp-rep.org/ Дата обращения 12.09.23.