Sciact
  • EN
  • RU

Полиномиальный алгоритм с асимптотической оценкой точности 2/3 для несимметричной задачи об m коммивояжёрах на максимум Full article

Journal Дискретный анализ и исследование операций
ISSN: 1560-7542
Output data Year: 2020, Volume: 27, Number: 3, Pages: 28–52 Pages count : 25
Tags гамильтонов цикл; задача коммивояжёра; задача нескольких коммивояжёров; приближённый алгоритм; гарантированная оценка точности
Authors Глебов А.Н. 1,2 , Токтохоева С.Г. 2
Affiliations
1 Институт математики им. С. Л. Соболева
2 Новосибирский государственный университет

Abstract: В 2005 г. Капланом и др. был разработан полиномиальный алгоритм с гарантированной оценкой точности 2/3 для несимметричного случая задачи коммивояжёра на максимум. В 2014 г. Глебов, Замбалаева и Скретнева получили алгоритм с такой же оценкой точности и кубической оценкой временной сложности для несимметричного случая задачи о двух коммивояжёрах на максимум, где требуется найти два рёберно не пересекающихся гамильтоновых цикла максимального суммарного веса в полном взвешенном n-вершинном ориентированном графе. Целью настоящей работы является построение аналогичного алгоритма для более общей задачи об m коммивояжёрах на максимум в несимметричном случае и обоснование для этого алгоритма оценки точности, асимптотически стремящейся к 2/3 с ростом m, и оценки временной сложности O(mn^3). Ил. 2, библиогр. 29. © А. Н. Глебов, С. Г. Токтохоева, 2020
Cite: Глебов А.Н. , Токтохоева С.Г.
Полиномиальный алгоритм с асимптотической оценкой точности 2/3 для несимметричной задачи об m коммивояжёрах на максимум
Дискретный анализ и исследование операций. 2020. Т.27. №3. С.28–52.
Translated: Glebov A.N. , Toktokhoeva S.G.
A Polynomial Algorithm with Asymptotic Ratio 2/3 for the Asymmetric Maximization Version of the m-PSP
Journal of Applied and Industrial Mathematics. 2020. V.14. N3. P.456-469. DOI: 10.1134/S1990478920030059 Scopus OpenAlex
Dates:
Submitted: Dec 2, 2019
Accepted: May 25, 2020
Identifiers: No identifiers
Citing: Пока нет цитирований