- PII
- 10.31857/S268695432360218X-1
- DOI
- 10.31857/S268695432360218X
- Publication type
- Status
- Published
- Authors
- Volume/ Edition
- Volume 514 / Issue number 1
- Pages
- 89-97
- 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
- асимметричная задача коммивояжера приближенные алгоритмы константная оценка точности задача о штейнеровском цикле минимального веса задача маршрутизации транспорта задача о покрытии графа ограниченным числом циклов
- Date of publication
- 01.01.2023
- Year of publication
- 2023
- Number of purchasers
- 0
- Views
- 57
References
- 1. Gutin G., Punnen A.P. The Traveling Salesman Problem and Its Variations. Springer US, Boston, MA, 2007.
- 2. Toth P., Vigo D. Vehicle Routing. Problems, Methods, and Applications. SIAM, Philadelphia, 2014.
- 3. 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.
- 4. Gendreau M., Potvin J.-Y. Handbook of Metaheuristics. Springer. 2019.
- 5. Vazirani V. Approximation algorithms. Springer. Berlin. 2003.
- 6. Williamson D.P., Shmoys D.B. The Design of Approximation Algorithms. New York, USA, 2011.
- 7. 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.
- 8. Сердюков А.И. О некоторых экстремальных обходах в графах // Управляемые системы. 1978. Т. 17. С. 76–79.
- 9. 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.
- 10. 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.
- 11. 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.
- 12. 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.
- 13. 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.
- 14. 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.
- 15. Хачай М.Ю., Незнахина Е.Д., Рыженко К.В. Полиномиальная аппроксимируемость асимметричной задачи о покрытии графа ограниченным числом циклов // Труды Института математики и механики УрО РАН. 2023. Т. 29. № 3. С. 261–273.
- 16. 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.
- 17. Papadimitriou C. Euclidean TSP is NP-complete // Theoret. Comput. Sci. 1977. V. 4. P. 237–244.
- 18. 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.
- 19. Khachay M., Neznakhina K. Approximability of the Minimum-Weight -Size Cycle Cover Problem // J. of Global Optimization. 2016. V. 66. № 1. P. 65–82.
- 20. VRP-REP: the vehicle routing problem repository. http://www.vrp-rep.org/ Дата обращения 12.09.23.
