|
Дискретн. анализ и исслед. опер., 2019, том 26, номер 2, страницы 30–59
(Mi da922)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Полиномиальный $3/5$-приближённый алгоритм для несимметричной задачи о трёх коммивояжёрах на максимум
А. Н. Глебовab, С. Г. Токтохоеваb a Институт математики им. С. Л. Соболева, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
b Новосибирский государственный университет, ул. Пирогова, 1, 630090 Новосибирск, Россия
Аннотация:
Разработан первый полиномиальный приближённый алгоритм с гарантированной оценкой точности для несимметричного случая задачи о трёх коммивояжёрах на максимум, где требуется найти три рёберно непересекающихся гамильтоновых цикла максимального суммарного веса в полном взвешенном ориентированном графе. Для полученного алгоритма обоснована гарантированная оценка точности $\frac 35$ и кубическая оценка временной сложности. Ил. 18, библиогр. 27.
Ключевые слова:
гамильтонов цикл, задача коммивояжёра, задача нескольких коммивояжёров, приближённый алгоритм, гарантированная оценка точности.
Финансовая поддержка |
Номер гранта |
Российский фонд фундаментальных исследований  |
18-01-00353_a 18-01-00747_а |
Исследование выполнено при финансовой поддержке Российского фонда фундаментальных
исследований (проекты № 18–01–00353, 18–01–00747). |
DOI:
https://doi.org/10.33048/daio.2019.26.622
Полный текст:
PDF файл (595 kB)
Список литературы:
PDF файл
HTML файл
Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2019, 13:2, 219–238
Реферативные базы данных:
Тип публикации:
Статья
УДК:
519.8 Статья поступила: 06.06.2018 Переработанный вариант: 27.11.2018 Принята к публикации: 28.11.2018
Образец цитирования:
А. Н. Глебов, С. Г. Токтохоева, “Полиномиальный $3/5$-приближённый алгоритм для несимметричной задачи о трёх коммивояжёрах на максимум”, Дискретн. анализ и исслед. опер., 26:2 (2019), 30–59; J. Appl. Industr. Math., 13:2 (2019), 219–238
Цитирование в формате AMSBIB
\RBibitem{GleTok19}
\by А.~Н.~Глебов, С.~Г.~Токтохоева
\paper Полиномиальный $3/5$-приближённый алгоритм для несимметричной задачи о~трёх~коммивояжёрах на максимум
\jour Дискретн. анализ и исслед. опер.
\yr 2019
\vol 26
\issue 2
\pages 30--59
\mathnet{http://mi.mathnet.ru/da922}
\crossref{https://doi.org/10.33048/daio.2019.26.622}
\transl
\jour J. Appl. Industr. Math.
\yr 2019
\vol 13
\issue 2
\pages 219--238
\crossref{https://doi.org/10.1134/S1990478919020042}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85067404465}
Образцы ссылок на эту страницу:
http://mi.mathnet.ru/da922 http://mi.mathnet.ru/rus/da/v26/i2/p30
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
А. Н. Глебов, С. Г. Токтохоева, “Полиномиальный алгоритм с асимптотической оценкой точности $2/3$ для несимметричной задачи об $m$ коммивояжёрах на максимум”, Дискретн. анализ и исслед. опер., 27:3 (2020), 28–52
; A. N. Glebov, S. G. Toktokhoeva, “A polynomial algorithm with asymptotic ratio $2/3$ for the asymmetric maximization version of the $m$-PSP”, J. Appl. Industr. Math., 14:3 (2020), 456–469
|
Просмотров: |
Эта страница: | 112 | Полный текст: | 9 | Литература: | 15 | Первая стр.: | 6 |
|