RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискретн. анализ и исслед. опер.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Дискретн. анализ и исслед. опер., сер. 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

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. А. Е. Бабурин, Э. Х. Гимади, “Об асимптотической точности эффективного алгоритма решения задачи $m$-PSP на максимум в многомерном eвклидовом пространстве”, Тр. ИММ УрО РАН, 16, № 3, 2010, 12–24  mathnet  elib; 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  crossref  isi
    2. А. Н. Глебов, Д. Ж. Замбалаева, “Полиномиальный алгоритм с оценкой точности $7/9$ для задачи о двух коммивояжёрах на максимум”, Дискретн. анализ и исслед. опер., 18:4 (2011), 17–48  mathnet  mathscinet  zmath; 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  crossref
    3. А. Н. Глебов, Д. Ж. Замбалаева, “Приближённый алгоритм решения задачи о двух коммивояжёрах на минимум с различными весовыми функциями”, Дискретн. анализ и исслед. опер., 18:5 (2011), 11–37  mathnet  mathscinet  zmath; 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  crossref
    4. А. Н. Глебов, А. В. Гордеева, Д. Ж. Замбалаева, “Алгоритм с оценкой 7/5 для задачи о двух коммивояжерах на минимум с различными весовыми функциями”, Сиб. электрон. матем. изв., 8 (2011), 296–309  mathnet
    5. Э. Х. Гимади, Е. В. Ивонина, “Приближённые алгоритмы решения задачи о двух коммивояжёрах на максимум”, Дискретн. анализ и исслед. опер., 19:1 (2012), 17–32  mathnet  mathscinet; 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  crossref
    6. Товстик Т.М., Жукова Е.В., “Алгоритм приближенного решения задачи коммивояжера”, Вестник санкт-петербургского университета. серия 1: математика. механика. астрономия, 2013, № 1, 101–109  mathscinet  elib
    7. Э. Х. Гимади, А. М. Истомин, И. А. Рыков, “О задаче нескольких коммивояжёров с ограничениями на пропускные способности рёбер графа”, Дискретн. анализ и исслед. опер., 20:5 (2013), 13–30  mathnet  mathscinet; E. Kh. Gimadi, A. M. Istomin, I. A. Rykov, “On $m$-capacitated peripatetic salesman problem”, J. Appl. Industr. Math., 8:1 (2014), 40–52  crossref
    8. Э. Х. Гимади, А. В. Кельманов, А. В. Пяткин, М. Ю. Хачай, “Эффективные алгоритмы с оценками точности для некоторых задач поиска нескольких клик в полном неориентированном взвешенном графе”, Тр. ИММ УрО РАН, 20, № 2, 2014, 99–112  mathnet  mathscinet  elib; 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  crossref  isi
    9. 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  crossref  mathscinet  zmath  isi  elib  scopus
    10. Э. Х. Гимади, А. М. Истомин, И. А. Рыков, “Задача о двух коммивояжерах с ограничениями на пропускные способности ребер графа с различными весовыми функциями”, Вестн. НГУ. Сер. матем., мех., информ., 14:3 (2014), 3–18  mathnet
    11. 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  crossref  mathscinet  zmath  isi  elib  scopus
    12. 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  crossref  mathscinet  zmath  isi  elib  scopus
    13. Э. Х. Гимади, О. Ю. Цидулко, “Асимптотически точный алгоритм для задачи нескольких коммивояжёров на случайных входных данных с дискретным распределением”, Дискретн. анализ и исслед. опер., 24:3 (2017), 5–19  mathnet  crossref  elib; 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  crossref
    14. А. Н. Глебов, С. Г. Токтохоева, “Полиномиальный $3/5$-приближённый алгоритм для несимметричной задачи о трёх коммивояжёрах на максимум”, Дискретн. анализ и исслед. опер., 26:2 (2019), 30–59  mathnet  crossref; 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  crossref
    15. А. Н. Глебов, С. Г. Токтохоева, “Полиномиальный алгоритм с асимптотической оценкой точности $2/3$ для несимметричной задачи об $m$ коммивояжёрах на максимум”, Дискретн. анализ и исслед. опер., 27:3 (2020), 28–52  mathnet  crossref; 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  crossref
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:429
    Полный текст:156
    Литература:50
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021