Полиномиальный 3/5-приближённый алгоритм для несимметричной задачи о трёх коммивояжёрах на максимум Full article
| Journal |
Дискретный анализ и исследование операций
ISSN: 1560-7542 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2019, Volume: 26, Number: 2, Pages: 30-59 Pages count : 30 | ||||
| Tags | гамильтонов цикл; задача коммивояжёра; задача нескольких коммивояжёров; приближённый алгоритм; гарантированная оценка точности | ||||
| Authors |
|
||||
| Affiliations |
|
Abstract:
Разработан первый полиномиальный приближённый алгоритм с гарантированной оценкой точности для несимметричного случая задачи о трёх коммивояжёрах на максимум, где требуется найти три рёберно непересекающихся гамильтоновых цикла максимального суммарного веса в полном взвешенном
ориентированном графе. Для полученного алгоритма обоснована гарантированная оценка точности 3/5 и кубическая оценка временной сложности. © А. Н. Глебов, С. Г. Токтохоева, 2019
Cite:
Глебов А.Н.
, Токтохоева С.Г.
Полиномиальный 3/5-приближённый алгоритм для несимметричной задачи о трёх коммивояжёрах на максимум
Дискретный анализ и исследование операций. 2019. Т.26. №2. С.30-59.
Полиномиальный 3/5-приближённый алгоритм для несимметричной задачи о трёх коммивояжёрах на максимум
Дискретный анализ и исследование операций. 2019. Т.26. №2. С.30-59.
Translated:
Glebov A.N.
, Toktokhoeva S.G.
A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP
Journal of Applied and Industrial Mathematics. 2019. V.13. N2. P.219-238. DOI: 10.1134/S1990478919020042 Scopus OpenAlex
A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP
Journal of Applied and Industrial Mathematics. 2019. V.13. N2. P.219-238. DOI: 10.1134/S1990478919020042 Scopus OpenAlex
Dates:
| Submitted: | Jun 6, 2018 |
| Accepted: | Nov 28, 2018 |
Identifiers:
No identifiers
Citing:
Пока нет цитирований