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

Authors: Neznakhina E.D.¹^,2, Ogorodnikov Y.Y.¹^,2, Rizhenko K.V.¹, Khachay M.Y.¹
Affiliations:
1. N.N. Krasovskii Institute of Mathematics and Mechanics
2. Ural federal university
Issue: Vol 514, No 1 (2023)
Pages: 89-97
Section: МАТЕМАТИКА
URL: https://journals.rcsi.science/2686-9543/article/view/247096
DOI: https://doi.org/10.31857/S268695432360218X
EDN: https://elibrary.ru/CYSMDZ
ID: 247096

Cite item

Full Text

Open Access
Restricted Access

Access granted
Restricted Access

Subscription Access

Abstract
About the authors
References
Supplementary files
Statistics

Abstract

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.

Keywords

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

References

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.