|
|
Дискретн. анализ и исслед. опер., 2009, том 16, номер 4, страницы 3–20
(Mi da576)
|
|
|
 |
Эта публикация цитируется в 6 научных статьях (всего в 6 статьях)
Приближённый алгоритм решения метрической задачи о двух коммивояжёрах с оценкой точности 2
А. А. Агеевab, А. В. Пяткинab
a Институт математики им. С. Л. Соболева СО РАН, г. Новосибирск, Россия
b Новосибирский государственный университет, г. Новосибирск, Россия
Аннотация:
В задаче $m$-PSP требуется в заданном $n$-вершинном полном неориентированном взвешенном графе найти $m$ непересекающихся гамильтоновых циклов наименьшего суммарного веса. Эта задача была впервые рассмотрена Крарупом в 1974 г.; она имеет применения в задачах дизайна сетей и теории расписаний. Известно, что задача 2-PSP NP-трудна даже в метрическом случае, а в общем случае для неё не существует приближённого алгоритма с точностью, ограниченной константным множителем. Бабурин, Гимади и Коркишко (2004) предложили приближённый алгоритм с точностью $(9/4+\varepsilon)$ для метрической задачи 2-PSP, основанный на решении задачи коммивояжёра. В настоящей статье представлен улучшенный приближённый алгоритм с точностью 2 и временем работы $O(n^2\log n)$ для метрической задачи 2-PSP. Этот алгоритм использует тот факт, что задача поиска двух непересекающихся остовных деревьев минимального суммарного веса является полиномиально разрешимой. Ил. 5, библиогр. 12.
Ключевые слова:
приближённый алгоритм, гамильтонов цикл, остовное дерево, задача коммивояжёра.
 Полный текст:
PDF файл (335 kB)
Список литературы:
PDF файл
HTML файл
Реферативные базы данных:
 
УДК:
519.178
Статья поступила: 21.02.2009
Переработанный вариант: 12.05.2009
Образец цитирования:
А. А. Агеев, А. В. Пяткин, “Приближённый алгоритм решения метрической задачи о двух коммивояжёрах с оценкой точности 2”, Дискретн. анализ и исслед. опер., 16:4 (2009), 3–20
Цитирование в формате AMSBIB
\RBibitem{AgePya09}
\by А.~А.~Агеев, А.~В.~Пяткин
\paper Приближённый алгоритм решения метрической задачи о~двух коммивояжёрах с~оценкой точности~2
\jour Дискретн. анализ и исслед. опер.
\yr 2009
\vol 16
\issue 4
\pages 3--20
\mathnet{http://mi.mathnet.ru/da576}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2589404}
\zmath{https://zbmath.org/?q=an:1249.90296}
Образцы ссылок на эту страницу:
http://mi.mathnet.ru/da576 http://mi.mathnet.ru/rus/da/v16/i4/p3
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
А. Е. Бабурин, Э. Х. Гимади, “Об асимптотической точности эффективного алгоритма решения задачи $m$-PSP на максимум в многомерном eвклидовом пространстве”, Тр. ИММ УрО РАН, 16, № 3, 2010, 12–24
  ; A. E. Baburin, E. Kh. Gimadi, “On the asymptotic accuracy of an algorithm for solving the $m$-PSP maximum problem in a multidimensional Euclidean space”, Proc. Steklov Inst. Math. (Suppl.), 272, suppl. 1 (2011), S1–S13   -
Э. Х. Гимади, А. М. Истомин, И. А. Рыков, “О задаче нескольких коммивояжёров с ограничениями на пропускные способности рёбер графа”, Дискретн. анализ и исслед. опер., 20:5 (2013), 13–30 ; E. Kh. Gimadi, A. M. Istomin, I. A. Rykov, “On $m$-capacitated peripatetic salesman problem”, J. Appl. Industr. Math., 8:1 (2014), 40–52
-
Э. Х. Гимади, А. М. Истомин, И. А. Рыков, “Задача о двух коммивояжерах с ограничениями на пропускные способности ребер графа с различными весовыми функциями”, Вестн. НГУ. Сер. матем., мех., информ., 14:3 (2014), 3–18
-
Э. Х. Гимади, О. Ю. Цидулко, “Асимптотически точный алгоритм для задачи нескольких коммивояжёров на случайных входных данных с дискретным распределением”, Дискретн. анализ и исслед. опер., 24:3 (2017), 5–19 ; E. Kh. Gimadi, O. Yu. Tsidulko, “An asymptotically optimal algorithm for the $m$-peripatetic salesman problem on random inputs with discrete distribution”, J. Appl. Industr. Math., 11:3 (2017), 354–361
-
А. Н. Глебов, С. Г. Токтохоева, “Полиномиальный $3/5$-приближённый алгоритм для несимметричной задачи о трёх коммивояжёрах на максимум”, Дискретн. анализ и исслед. опер., 26:2 (2019), 30–59 ; A. N. Glebov, S. G. Toktokhoeva, “A polynomial $3/5$-approximate algorithm for the asymmetric maximization version of $3$-PSP”, J. Appl. Industr. Math., 13:2 (2019), 219–238
-
А. Н. Глебов, С. Г. Токтохоева, “Полиномиальный алгоритм с асимптотической оценкой точности $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
|
| Просмотров: |
| Эта страница: | 694 | | Полный текст: | 126 | | Литература: | 29 | | Первая стр.: | 15 |
|
Пользовательское соглашение