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

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

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



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






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


Дискретн. анализ и исслед. опер., 2011, том 18, номер 4, страницы 17–48 (Mi da658)  

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

Полиномиальный алгоритм с оценкой точности $7/9$ для задачи о двух коммивояжёрах на максимум

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

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

Аннотация: Рассматривается задача об отыскании в полном неориентированном графе двух рёберно-непересекающихся гамильтоновых циклов с максимальным суммарным весом рёбер. Для этой задачи получен алгоритм с гарантированной оценкой точности $7/9$, наилучшей на сегодняшний день, и кубической временно́й сложностью. В случае, когда веса рёбер графа принимают значения из заданного промежутка $[1,q]$, разработана модификация алгоритма, имеющая оценку точности $(7q+3)/(9q+1)$, также наилучшую на сегодняшний день, и кубическую временну́ю сложность. Ил. 5, библиогр. 14.

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

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

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

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

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

Образец цитирования: А. Н. Глебов, Д. Ж. Замбалаева, “Полиномиальный алгоритм с оценкой точности $7/9$ для задачи о двух коммивояжёрах на максимум”, Дискретн. анализ и исслед. опер., 18:4 (2011), 17–48; J. Appl. Industr. Math., 6:1 (2012), 69–89

Цитирование в формате AMSBIB
\RBibitem{GleZam11}
\by А.~Н.~Глебов, Д.~Ж.~Замбалаева
\paper Полиномиальный алгоритм с~оценкой точности $7/9$ для задачи о~двух коммивояж\"ерах на максимум
\jour Дискретн. анализ и исслед. опер.
\yr 2011
\vol 18
\issue 4
\pages 17--48
\mathnet{http://mi.mathnet.ru/da658}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2894339}
\zmath{https://zbmath.org/?q=an:1249.90300}
\transl
\jour J. Appl. Industr. Math.
\yr 2012
\vol 6
\issue 1
\pages 69--89
\crossref{https://doi.org/10.1134/S1990478912010085}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84857682297}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da658
  • http://mi.mathnet.ru/rus/da/v18/i4/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. Э. Х. Гимади, Е. В. Ивонина, “Приближённые алгоритмы решения задачи о двух коммивояжёрах на максимум”, Дискретн. анализ и исслед. опер., 19:1 (2012), 17–32  mathnet  mathscinet; E. Kh. Gimadi, E. V. Ivonina, “Approximation algorithms for maximum-weight problem of two-peripatetic salesmen”, J. Appl. Industr. Math., 6:3 (2012), 295–305  crossref
    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. О. Ю. Цидулко, “О разрешимости $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
    4. Э. Х. Гимади, Ю. В. Глазков, О. Ю. Цидулко, “Вероятностный анализ алгоритма решения трёхиндексной $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
    5. А. Н. Глебов, Д. Ж. Замбалаева, А. А. Скретнева, “$2/3$-приближённый алгоритм для несимметричной задачи о двух коммивояжёрах на максимум”, Дискретн. анализ и исслед. опер., 21:6 (2014), 11–20  mathnet  mathscinet; A. N. Glebov, D. Zh. Zambalaeva, A. A. Skretneva, “$2/3$-approximation algorithm for the maximization version of the asymmetric two peripatetic salesman problem”, J. Appl. Industr. Math., 9:1 (2015), 61–67  crossref
    6. Э. Х. Гимади, А. М. Истомин, И. А. Рыков, “Задача о двух коммивояжерах с ограничениями на пропускные способности ребер графа с различными весовыми функциями”, Вестн. НГУ. Сер. матем., мех., информ., 14:3 (2014), 3–18  mathnet
    7. 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
    8. Э. Х. Гимади, О. Ю. Цидулко, “Асимптотически точный алгоритм для задачи нескольких коммивояжёров на случайных входных данных с дискретным распределением”, Дискретн. анализ и исслед. опер., 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
    9. 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
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:361
    Полный текст:61
    Литература:34
    Первая стр.:5
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019