|
|
Дискретн. анализ и исслед. опер., сер. 2, 2007, том 14, номер 2, страницы 41–61
(Mi da514)
|
 |
|
 |
Эта публикация цитируется в 15 научных статьях (всего в 15 статьях)
Алгоритмы приближённого решения задачи о двух коммивояжёрах в полном графе с весами рёбер 1 и 2
Э. Х. Гимади, Ю. В. Глазков, А. Н. Глебов
Институт математики им. С. Л. Соболева СО РАН
Аннотация:
Рассматривается задача отыскания двух рёберно непересекающихся гамильтоновых циклов минимального суммарного веса в полном неориентированном графе с произвольно приписанными весами рёбер 1 и 2. Основной результат работы – описание полиномиальных алгоритмов с гарантированными оценками точности 26/21 и 6/5, наилучшими в настоящее время. Эти алгоритмы основаны на нахождении частичных туров с большим числом рёбер в графах специального вида. Библ. 13.
 Полный текст:
PDF файл (329 kB)
Список литературы:
PDF файл
HTML файл
Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2009, 3:1, 46–60
Реферативные базы данных:
 
УДК:
519.8
Статья поступила: 18.08.2007
Переработанный вариант: 09.11.2007
Образец цитирования:
Э. Х. Гимади, Ю. В. Глазков, А. Н. Глебов, “Алгоритмы приближённого решения задачи о двух коммивояжёрах в полном графе с весами рёбер 1 и 2”, Дискретн. анализ и исслед. опер., сер. 2, 14:2 (2007), 41–61; J. Appl. Industr. Math., 3:1 (2009), 46–60
Цитирование в формате AMSBIB
\RBibitem{GimGlaGle07}
\by Э.~Х.~Гимади, Ю.~В.~Глазков, А.~Н.~Глебов
\paper Алгоритмы приближённого решения задачи о~двух коммивояжёрах в~полном графе с~весами рёбер~1 и~2
\jour Дискретн. анализ и исслед. опер., сер.~2
\yr 2007
\vol 14
\issue 2
\pages 41--61
\mathnet{http://mi.mathnet.ru/da514}
\zmath{https://zbmath.org/?q=an:1249.05364}
\transl
\jour J. Appl. Industr. Math.
\yr 2009
\vol 3
\issue 1
\pages 46--60
\crossref{https://doi.org/10.1134/S1990478909010074}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-63349098253}
Образцы ссылок на эту страницу:
http://mi.mathnet.ru/da514 http://mi.mathnet.ru/rus/da/v14/s2/i2/p41
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  -
А. Н. Глебов, Д. Ж. Замбалаева, “Полиномиальный алгоритм с оценкой точности $7/9$ для задачи о двух коммивояжёрах на максимум”, Дискретн. анализ и исслед. опер., 18:4 (2011), 17–48
 ; A. N. Glebov, D. Zh. Zambalayeva, “Polynomial algorithm with approximation ratio $7/9$ for maximum 2-PSP”, J. Appl. Industr. Math., 6:1 (2012), 69–89 -
А. Н. Глебов, Д. Ж. Замбалаева, “Приближённый алгоритм решения задачи о двух коммивояжёрах на минимум с различными весовыми функциями”, Дискретн. анализ и исслед. опер., 18:5 (2011), 11–37 ; A. N. Glebov, D. Zh. Zambalayeva, “An approximation algorithm for the minimum 2-PSP with different weight functions valued 1 and 2”, J. Appl. Industr. Math., 6:2 (2012), 167–183
-
А. Н. Глебов, А. В. Гордеева, Д. Ж. Замбалаева, “Алгоритм с оценкой 7/5 для задачи о двух коммивояжерах на минимум с различными весовыми функциями”, Сиб. электрон. матем. изв., 8 (2011), 296–309
-
Э. Х. Гимади, Е. В. Ивонина, “Приближённые алгоритмы решения задачи о двух коммивояжёрах на максимум”, Дискретн. анализ и исслед. опер., 19:1 (2012), 17–32 ; E. Kh. Gimadi, E. V. Ivonina, “Approximation algorithms for maximum-weight problem of two-peripatetic salesmen”, J. Appl. Industr. Math., 6:3 (2012), 295–305
-
Товстик Т.М., Жукова Е.В., “Алгоритм приближенного решения задачи коммивояжера”, Вестник санкт-петербургского университета. серия 1: математика. механика. астрономия, 2013, № 1, 101–109
-
Э. Х. Гимади, А. М. Истомин, И. А. Рыков, “О задаче нескольких коммивояжёров с ограничениями на пропускные способности рёбер графа”, Дискретн. анализ и исслед. опер., 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
-
Э. Х. Гимади, А. В. Кельманов, А. В. Пяткин, М. Ю. Хачай, “Эффективные алгоритмы с оценками точности для некоторых задач поиска нескольких клик в полном неориентированном взвешенном графе”, Тр. ИММ УрО РАН, 20, № 2, 2014, 99–112 ; E. Kh. Gimadi, A. V. Kel'manov, A. V. Pyatkin, M. Yu. Khachai, “Efficient algorithms with performance estimates for some problems of finding several cliques in a complete undirected weighted graph”, Proc. Steklov Inst. Math. (Suppl.), 289, suppl. 1 (2015), 88–101
-
Michallet J. Prins Ch. Amodeo L. Yalaoui F. Vitry G., “Multi-Start Iterated Local Search for the Periodic Vehicle Routing Problem with Time Windows and Time Spread Constraints on Services”, Comput. Oper. Res., 41 (2014), 196–207
-
Э. Х. Гимади, А. М. Истомин, И. А. Рыков, “Задача о двух коммивояжерах с ограничениями на пропускные способности ребер графа с различными весовыми функциями”, Вестн. НГУ. Сер. матем., мех., информ., 14:3 (2014), 3–18
-
Gimadi E.Kh. Glebov A.N. Skretneva A.A. Tsidulko O.Yu. Zambalaeva D.Zh., “Combinatorial Algorithms With Performance Guarantees For Finding Several Hamiltonian Circuits in a Complete Directed Weighted Graph”, Discrete Appl. Math., 196:SI (2015), 54–61
-
Khachai M.Yu., Neznakhina E.D., “Approximability of the Problem About a Minimum-Weight Cycle Cover of a Graph”, Dokl. Math., 91:2 (2015), 240–245
-
Э. Х. Гимади, О. Ю. Цидулко, “Асимптотически точный алгоритм для задачи нескольких коммивояжёров на случайных входных данных с дискретным распределением”, Дискретн. анализ и исслед. опер., 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
|
| Просмотров: |
| Эта страница: | 429 | | Полный текст: | 156 | | Литература: | 50 |
|
Пользовательское соглашение