Оптимизация параметров полиномиального рандомизированного алгоритма для асимметричной задачи коммивояжера - Баркетов, Максим Сергеевич (Журнал Белорусского государственного университета. Математика. Информатика, 2024)
Рассматривается асимметричная задача коммивояжера, в которой надо найти гамильтонов цикл с минимальной суммарной стоимостью дуг в полном ориентированном графе. Для решения данной задачи на основе алгоритма, построенного автором в статье «Полиномиальный рандомизированный алгоритм для задачи “Асимметричный коммивояжер”» (Доклады Национальной академии наук Беларуси. 2022. Т. 66, № 5. С. 489 – 494), разработан новый параметризованный полиномиальный рандомизированный алгоритм. Его отличие состоит в другой параметризации. Однако основным результатом является препроцессинговый полиномиальный алгоритм линейного программирования для определения оптимальных параметров.
Keywords: комбинаторная оптимизация; теория вероятностей; рандомизированный алгоритм; приближенный алгоритм; задача коммивояжера