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

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

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



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






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


Вестн. НГУ. Сер. матем., мех., информ., 2014, том 14, выпуск 3, страницы 3–18 (Mi vngu341)  

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

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

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

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

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

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

Полный текст: PDF файл (307 kB)
Список литературы: PDF файл   HTML файл
Тип публикации: Статья
УДК: 519.8
Поступила в редакцию: 16.12.2013

Образец цитирования: Э. Х. Гимади, А. М. Истомин, И. А. Рыков, “Задача о двух коммивояжерах с ограничениями на пропускные способности ребер графа с различными весовыми функциями”, Вестн. НГУ. Сер. матем., мех., информ., 14:3 (2014), 3–18

Цитирование в формате AMSBIB
\RBibitem{GimIstRyk14}
\by Э.~Х.~Гимади, А.~М.~Истомин, И.~А.~Рыков
\paper Задача о двух коммивояжерах с ограничениями на пропускные способности ребер графа с различными весовыми функциями
\jour Вестн. НГУ. Сер. матем., мех., информ.
\yr 2014
\vol 14
\issue 3
\pages 3--18
\mathnet{http://mi.mathnet.ru/vngu341}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/vngu341
  • http://mi.mathnet.ru/rus/vngu/v14/i3/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. В. М. Неделько, “К вопросу об эффективности бустинга в задаче классификации”, Вестн. НГУ. Сер. матем., мех., информ., 15:2 (2015), 72–89  mathnet  crossref
  • Вестник Новосибирского государственного университета. Серия: математика, механика, информатика
    Просмотров:
    Эта страница:175
    Полный текст:28
    Литература:30
    Первая стр.:12
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020