Аннотация:
В статье впервые обосновываются алгоритмы с постоянными гарантированными
оценками точности для серии асимметричных маршрутных задач
комбинаторной оптимизации:
задачи о штейнеровском цикле (SCP), обобщенной задачи коммивояжера (GTSP),
задачи маршрутизации транспорта с неделимым потребительским спросом
(CVRP-UCD) и задачи коммивояжера с призами (PCTSP).
Объединяет представленные результаты то, что все они опираются
на полиномиальную сводимость, сохраняющую стоимость
(cost-preserving reduction), исследуемых задач к подходящим постановкам асимметричной задачи коммивояжера (ATSP) и
(22+ε)-приближенный алгоритм для этой классической задачи,
предложенный О. Свенссоном и В. Трауб в 2019 г.
Ключевые слова:
асимметричная задача коммивояжера, алгоритм с постоянной оценкой точности, полиномиальная сводимость, задача о штейнеровском цикле минимального веса, обобщенная задача коммивояжера, задача коммивояжера с призами, задача маршрутизации транспорта.
Образец цитирования:
М. Ю. Хачай, Е. Д. Незнахина, К. В. Рыженко, “Приближенные алгоритмы с постоянной точностью для серии маршрутных комбинаторных задач, основанные на сведении к асимметричной задаче коммивояжера”, Тр. ИММ УрО РАН, 28, № 3, 2022, 241–258; Proc. Steklov Inst. Math. (Suppl.), 319, suppl. 1 (2022), S140–S155
\RBibitem{KhaNezRyz22}
\by М.~Ю.~Хачай, Е.~Д.~Незнахина, К.~В.~Рыженко
\paper Приближенные алгоритмы с постоянной точностью для серии маршрутных комбинаторных задач, основанные на сведении к асимметричной задаче коммивояжера
\serial Тр. ИММ УрО РАН
\yr 2022
\vol 28
\issue 3
\pages 241--258
\mathnet{http://mi.mathnet.ru/timm1940}
\crossref{https://doi.org/10.21538/0134-4889-2022-28-3-241-258}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4488895}
\elib{https://elibrary.ru/item.asp?id=49352764}
\transl
\jour Proc. Steklov Inst. Math. (Suppl.)
\yr 2022
\vol 319
\issue , suppl. 1
\pages S140--S155
\crossref{https://doi.org/10.1134/S0081543822060128}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000905214000018}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85163006876}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/timm1940
https://www.mathnet.ru/rus/timm/v28/i3/p241
Эта публикация цитируется в следующих 5 статьяx:
Ksenia Rizhenko, “Improved first player strategy for the zero-sum sequential uncrossing game”, Ural Math. J., 10:1 (2024), 136–146
Manal EL Jaouhari, Ghita Bencheikh, Ghizlane Bencheikh, Lecture Notes in Networks and Systems, 1105, Proceeding of the 7th International Conference on Logistics Operations Management, GOL'24, 2024, 68
Daniil Khachai, Katherine Neznakhina, Ksenia Rizhenko, Michael Khachay, “Fixed-Ratio Approximation Algorithm for the Minimum Cost Cover of a Digraph by Bounded Number of Cycles”, WSEAS TRANSACTIONS ON COMPUTERS, 23 (2024), 218
М. Ю. Хачай, Е. Д. Незнахина, К. В. Рыженко, “Полиномиальная аппроксимируемость асимметричной задачи о покрытии графа ограниченным числом циклов”, Тр. ИММ УрО РАН, 29, № 3, 2023, 261–273; M. Yu. Khachay, E. D. Neznakhina, K. V. Ryzhenko, “Polynomial-Time Approximability of the Asymmetric Problem of Covering a Graph by a Bounded Number of Cycles”, Proc. Steklov Inst. Math. (Suppl.), 323, suppl. 1 (2023), S121–S132
Е. Д. Незнахина, Ю. Ю. Огородников, К. В. Рыженко, М. Ю. Хачай, “Приближенные алгоритмы с фиксированными оценками точности для серии асимметричных задач маршрутизации”, Докл. РАН. Матем., информ., проц. упр., 514:1 (2023), 89–97; E. D. Neznakhina, Yu. Yu. Ogorodnikov, K. V. Ryzhenko, M. Yu. Khachay, “Approximation algorithms with constant factors for a series of asymmetric routing problems”, Dokl. Math., 108:3 (2023), 499–505
Цитирование в формате AMSBIB
Обратная связь: