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

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

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



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






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


Дискретн. анализ и исслед. опер., 2011, том 18, номер 5, страницы 11–37 (Mi da663)  

Эта публикация цитируется в 6 научных статьях (всего в 6 статьях)

Приближённый алгоритм решения задачи о двух коммивояжёрах на минимум с различными весовыми функциями

А. Н. Глебовab, Д. Ж. Замбалаеваa

a Институт математики им. С. Л. Соболева СО РАН, Новосибирск, Россия
b Новосибирский гос. университет, Новосибирск, Россия

Аннотация: Основной результат статьи – приближённый алгоритм с оценкой временно́й сложности $O(n^5)$ и оценкой точности 4/3 (без учёта аддитивной константы) для задачи о поиске двух рёберно непересекающихся гамильтоновых циклов минимального суммарного веса в полном $n$-вершинном графе с весами рёбер 1 и 2 в случае, когда весовые функции рёбер этих циклов различны (задача о двух коммивояжёрах на минимум с весами рёбер 1 и 2). Этот результат улучшает ранее установленную для задачи оценку точности 11/7. Ил. 3, библиогр. 10.

Ключевые слова: задача коммивояжёра, задача о двух коммивояжёрах, полиномиальный алгоритм, гарантированная оценка точности.

Полный текст: PDF файл (451 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2012, 6:2, 167–183

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.8
Статья поступила: 23.06.2011

Образец цитирования: А. Н. Глебов, Д. Ж. Замбалаева, “Приближённый алгоритм решения задачи о двух коммивояжёрах на минимум с различными весовыми функциями”, Дискретн. анализ и исслед. опер., 18:5 (2011), 11–37; J. Appl. Industr. Math., 6:2 (2012), 167–183

Цитирование в формате AMSBIB
\RBibitem{GleZam11}
\by А.~Н.~Глебов, Д.~Ж.~Замбалаева
\paper Приближ\"енный алгоритм решения задачи о~двух коммивояж\"ерах на минимум с~различными весовыми функциями
\jour Дискретн. анализ и исслед. опер.
\yr 2011
\vol 18
\issue 5
\pages 11--37
\mathnet{http://mi.mathnet.ru/da663}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2918327}
\zmath{https://zbmath.org/?q=an:1249.90301}
\transl
\jour J. Appl. Industr. Math.
\yr 2012
\vol 6
\issue 2
\pages 167--183
\crossref{https://doi.org/10.1134/S1990478912020056}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84861773292}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da663
  • http://mi.mathnet.ru/rus/da/v18/i5/p11

    ОТПРАВИТЬ: 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. Э. Х. Гимади, А. М. Истомин, И. А. Рыков, “О задаче нескольких коммивояжёров с ограничениями на пропускные способности рёбер графа”, Дискретн. анализ и исслед. опер., 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
    2. О. Ю. Цидулко, “О разрешимости $8$-индексной аксиальной задачи о назначениях на одноциклических подстановках”, Дискретн. анализ и исслед. опер., 20:5 (2013), 66–83  mathnet  mathscinet; O. Yu. Tsidulko, “On solvability of the axial $8$-index assignment problem on one-cycle permutations”, J. Appl. Industr. Math., 8:1 (2014), 115–126  crossref  isi
    3. Э. Х. Гимади, Ю. В. Глазков, О. Ю. Цидулко, “Вероятностный анализ алгоритма решения трёхиндексной $m$-слойной планарной задачи о назначениях на одноциклических подстановках”, Дискретн. анализ и исслед. опер., 21:1 (2014), 15–29  mathnet  mathscinet; E. Kh. Gimadi, Yu. V. Glazkov, O. Yu. Tsidulko, “The probabilistic analysis of an algorithm for solving the $m$-planar $3$-dimensional assignment problem on one-cycle permutations”, J. Appl. Industr. Math., 8:2 (2014), 208–217  crossref  isi
    4. Э. Х. Гимади, А. М. Истомин, И. А. Рыков, “Задача о двух коммивояжерах с ограничениями на пропускные способности ребер графа с различными весовыми функциями”, Вестн. НГУ. Сер. матем., мех., информ., 14:3 (2014), 3–18  mathnet
    5. 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
    6. Э. Х. Гимади, О. Ю. Цидулко, “Асимптотически точный алгоритм для задачи нескольких коммивояжёров на случайных входных данных с дискретным распределением”, Дискретн. анализ и исслед. опер., 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
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:381
    Полный текст:75
    Литература:45
    Первая стр.:7
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019