- Код статьи
- 10.31857/S268695432360218X-1
- DOI
- 10.31857/S268695432360218X
- Тип публикации
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том 514 / Номер выпуска 1
- Страницы
- 89-97
- Аннотация
- Обосновываются первые алгоритмы с константными оценками точности для серии асимметричных постановок задач маршрутизации: задачи о штейнеровском цикле, задачи коммивояжера с призами, задачи о покрытии графа ограниченным числом циклов и др. В большинстве своем предложенные алгоритмы опираются на оригинальные схемы сведения исследуемых постановок к вспомогательным постановкам асимметричной задачи коммивояжера и прорывные результаты О. Свенссона, Я. Тарнавски, Л. Вега и В. Трауб, Й. Вигена в области эффективной аппроксимируемости данной задачи. Алгоритм для задачи о покрытии графа ограниченным числом циклов опирается на технику, связанную с более глубокой модификацией подхода Свенссона-Трауб.
- Ключевые слова
- асимметричная задача коммивояжера приближенные алгоритмы константная оценка точности задача о штейнеровском цикле минимального веса задача маршрутизации транспорта задача о покрытии графа ограниченным числом циклов
- Дата публикации
- 01.01.2023
- Год выхода
- 2023
- Всего подписок
- 0
- Всего просмотров
- 56
Библиография
- 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.
