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

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

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



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






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


Дискретн. анализ и исслед. опер., 2009, том 16, номер 4, страницы 3–20 (Mi da576)  

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

Приближённый алгоритм решения метрической задачи о двух коммивояжёрах с оценкой точности 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

    ОТПРАВИТЬ: 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. Э. Х. Гимади, А. М. Истомин, И. А. Рыков, “О задаче нескольких коммивояжёров с ограничениями на пропускные способности рёбер графа”, Дискретн. анализ и исслед. опер., 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
    3. Э. Х. Гимади, А. М. Истомин, И. А. Рыков, “Задача о двух коммивояжерах с ограничениями на пропускные способности ребер графа с различными весовыми функциями”, Вестн. НГУ. Сер. матем., мех., информ., 14:3 (2014), 3–18  mathnet
    4. Э. Х. Гимади, О. Ю. Цидулко, “Асимптотически точный алгоритм для задачи нескольких коммивояжёров на случайных входных данных с дискретным распределением”, Дискретн. анализ и исслед. опер., 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
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:651
    Полный текст:105
    Литература:28
    Первая стр.:15
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019