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

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

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



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






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


Дискретн. анализ и исслед. опер., 2013, том 20, номер 5, страницы 13–30 (Mi da743)  

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

О задаче нескольких коммивояжёров с ограничениями на пропускные способности рёбер графа

Э. Х. Гимадиab, А. М. Истоминa, И. А. Рыковab

a Институт математики им. С. Л. Соболева СО РАН, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
b Новосибирский гос. университет, ул. Пирогова, 2, 630090 Новосибирск, Россия

Аннотация: Рассматривается частный случай задачи отыскания $m$ гамильтоновых циклов с ограничениями на число повторений рёбер ($m$-Capacitated Peripatetic Salesman Problem, $m$-$\mathrm{CPSP}$) – задачи $2$-$\mathrm{CPSP}$ на минимум и максимум с весами рёбер из целочисленного сегмента $\{1,q\}$. Пропускные способности рёбер заданы независимыми случайными величинами, принимающими значение $2(1)$ с вероятностью $p(1-p)$. Построены алгоритмы решения задач $2$-$\mathrm{CPSP_{min}}$ и $2$-$\mathrm{CPSP_{max}}$ с гарантированными оценками точности в среднем по всем возможным входам. В частности, для задач на графах с весами рёбер $1$ и $2$ алгоритмы имеют оценки точности $(19-5p)/12$ и $(25+7p)/36$ в среднем по всем возможным входам для задачи на минимум и на максимум соответственно. Ил. 17, библиогр. 20.

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

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

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2014, 8:1, 40–52

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

Тип публикации: Статья
УДК: 519.8
Статья поступила: 27.12.2012
Переработанный вариант: 10.06.2013

Образец цитирования: Э. Х. Гимади, А. М. Истомин, И. А. Рыков, “О задаче нескольких коммивояжёров с ограничениями на пропускные способности рёбер графа”, Дискретн. анализ и исслед. опер., 20:5 (2013), 13–30; J. Appl. Industr. Math., 8:1 (2014), 40–52

Цитирование в формате AMSBIB
\RBibitem{GimIstRyk13}
\by Э.~Х.~Гимади, А.~М.~Истомин, И.~А.~Рыков
\paper О задаче нескольких коммивояжёров с~ограничениями на пропускные способности рёбер графа
\jour Дискретн. анализ и исслед. опер.
\yr 2013
\vol 20
\issue 5
\pages 13--30
\mathnet{http://mi.mathnet.ru/da743}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3184441}
\transl
\jour J. Appl. Industr. Math.
\yr 2014
\vol 8
\issue 1
\pages 40--52
\crossref{https://doi.org/10.1134/S1990478914010050}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84894299351}


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

    ОТПРАВИТЬ: 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. А. М. Истомин, “Вероятностный анализ одной задачи маршрутизации”, Дискретн. анализ и исслед. опер., 21:4 (2014), 42–53  mathnet  mathscinet
    2. Э. Х. Гимади, А. М. Истомин, И. А. Рыков, “Задача о двух коммивояжерах с ограничениями на пропускные способности ребер графа с различными весовыми функциями”, Вестн. НГУ. Сер. матем., мех., информ., 14:3 (2014), 3–18  mathnet
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:357
    Полный текст:80
    Литература:27
    Первая стр.:9

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019