Оптимизация параметров полиномиального рандомизированного алгоритма для асимметричной задачи коммивояжера

Авторы

  • Максим Сергеевич Баркетов Объединенный институт проблем информатики НАН Беларуси, ул. Сурганова, 6, 220012, г. Минск, Беларусь

Ключевые слова:

комбинаторная оптимизация, теория вероятностей, рандомизированный алгоритм, приближенный алгоритм, задача коммивояжера
Поддерживающие организации
Работа выполнена при частичной финансовой поддержке Белорусского республиканского фонда фундаментальных исследований (проекты Ф21-010 и Ф23РНФ-017).

Аннотация

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

Биография автора

  • Максим Сергеевич Баркетов, Объединенный институт проблем информатики НАН Беларуси, ул. Сурганова, 6, 220012, г. Минск, Беларусь

    кандидат физико-математических наук, доцент; старший научный сотрудник лаборатории математической кибернетики

Библиографические ссылки

  1. Barketau MS. Polynomial randomised algorithm for the asymmetric travelling salesman problem. Doklady of the National Academy of Sciences of Belarus. 2022;66(5):489–494. Russian. DOI: 10.29235/1561-8323-2022-66-5-489-494.
  2. Arora S. Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In: Proceedings of 37th Annual symposium on foundations of computer science; 1996 October 14–16; Burlington, USA. Los Alamitos: IEEE Computer Society Press; 1996. p. 2–11. DOI: 10.1109/sfcs.1996.548458.
  3. Svensson O. Approximating ATSP by relaxing connectivity. In: Proceedings of 2015 IEEE 56th Annual symposium on foundations of computer science (FOCS-2015); 2015 October 17–20; Berkeley, USA. Los Alamitos: Conference Publishing Services of the IEEE Computer Society; 2015. p. 1–19. DOI: 10.1109/focs.2015.10.
  4. Burke EK, Cowling PI, Keuthen R. Effective local and guided variable neighbourhood search methods for the asymmetric travelling salesman problem. In: Boers EJW, Cagnoni S, Gottlieb J, Hart E, Lanzi PL, Raidl GR, et al., editors. Applications of evolutionary computing. EvoWorkshops-2001: EvoCOP, EvoFlight, EvoIASP, EvoLearn, and EvoSTIM; 2001 April 18–20; Como, Italy. Berlin: Springer; 2001. p. 203–212 (Goos G, Hartmanis J, van Leeuwen J, editors. Lecture notes in computer science; volume 2037). DOI: 10.1007/3-540-45365-2_21.
  5. Fischetti M, Lodi A, Toth P. Exact methods for the asymmetric traveling salesman problem. In: Gutin G, Punnen AP, editors. The traveling salesman problem and its variations. New York: Springer; 2007. p. 169–205 (Du D-Z, Pardalos PM, editors. Combinatorial optimization; volume 12). DOI: 10.1007/0-306-48213-4_4.
  6. Grötschel M, Lovász L, Schrijver A. Geometric algorithms and combinatorial optimization. 2nd edition. Berlin: Springer-Verlag; 2012. XII, 362 p. (Graham RL, Korte B, Lovász L, editors. Algorithms and combinatorics; volume 2).

Загрузки

Дополнительные файлы

Опубликован

2024-07-23

Выпуск

№ 2 (2024): Журнал Белорусского государственного университета. Математика. Информатика

Раздел

Краткие сообщения

Лицензия

Авторы, публикующиеся в данном журнале, соглашаются со следующим:

  1. Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. Авторы сохраняют право заключать отдельные контрактные договоренности, касающиеся неэксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге) со ссылкой на ее оригинальную публикацию в этом журнале.
  3. Авторы имеют право размещать их работу в интернете (например, в институтском хранилище или на персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу. (См. The Effect of Open Access).

Как цитировать

[1]
Баркетов, М.С. 2024. Оптимизация параметров полиномиального рандомизированного алгоритма для асимметричной задачи коммивояжера. Журнал Белорусского государственного университета. Математика. Информатика. 2 (июл. 2024), 113–118.