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

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

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



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






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


Дискретн. анализ и исслед. опер., 2012, том 19, номер 1, страницы 17–32 (Mi da674)  

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

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

Э. Х. Гимадиab, Е. В. Ивонинаa

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

Аннотация: Рассматривается задача отыскания в полном неориентированном графе двух рёберно непересекающихся гамильтоновых циклов (маршрутов коммивояжёра) с максимальным суммарным весом. Для случая весов рёбер из отрезка $[1,q]$ представлен полиномиальный алгоритм с гарантированной оценкой точности $\frac{3q+2}{4q+1}$. В случае весов 1 и 2 и двух различных весовых функций, соответствующих двум маршрутам, предложен полиномиальный алгоритм с оценкой точности $\frac{11\rho-8}{18\rho-15}$, где $\rho$ – оценка точности некоторого алгоритма решения аналогичной задачи на минимум. Ил. 1, библиогр. 13.

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

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

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

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

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

Образец цитирования: Э. Х. Гимади, Е. В. Ивонина, “Приближённые алгоритмы решения задачи о двух коммивояжёрах на максимум”, Дискретн. анализ и исслед. опер., 19:1 (2012), 17–32; J. Appl. Industr. Math., 6:3 (2012), 295–305

Цитирование в формате AMSBIB
\RBibitem{GimIvo12}
\by Э.~Х.~Гимади, Е.~В.~Ивонина
\paper Приближ\"енные алгоритмы решения задачи о~двух коммивояж\"ерах на максимум
\jour Дискретн. анализ и исслед. опер.
\yr 2012
\vol 19
\issue 1
\pages 17--32
\mathnet{http://mi.mathnet.ru/da674}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2961449}
\transl
\jour J. Appl. Industr. Math.
\yr 2012
\vol 6
\issue 3
\pages 295--305
\crossref{https://doi.org/10.1134/S1990478912030040}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da674
  • http://mi.mathnet.ru/rus/da/v19/i1/p17

    ОТПРАВИТЬ: 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. Э. Х. Гимади, О. Ю. Цидулко, “Асимптотически точный алгоритм для задачи нескольких коммивояжёров на случайных входных данных с дискретным распределением”, Дискретн. анализ и исслед. опер., 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
    6. Gimadi E.Kh. Tsidulko O.Yu., “Approximation Algorithms For the Maximum M-Peripatetic Salesman Problem”, Analysis of Images, Social Networks and Texts, Aist 2017, Lecture Notes in Computer Science, 10716, ed. VanDerAalst W. Ignatov D. Khachay M. Kuznetsov S. Lempitsky V. Lomazova I. Loukachevitch N. Napoli A. Panchenko A. Pardalos P. Savchenko A. Wasserman S., Springer International Publishing Ag, 2018, 304–312  crossref  mathscinet  isi  scopus
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:522
    Полный текст:117
    Литература:25
    Первая стр.:9
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020