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

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

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



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






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


Сиб. электрон. матем. изв., 2011, том 8, страницы 296–309 (Mi semr325)  

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

Алгоритм с оценкой 7/5 для задачи о двух коммивояжерах на минимум с различными весовыми функциями

А. Н. Глебовa, А. В. Гордееваb, Д. Ж. Замбалаеваa

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

Аннотация: We present a cubic time algorithm with approximation ratio 7/5 (plus some additive constant) for the 2-Peripatetic Salesman Problem on minimum with different weight functions valued 1 and 2 (abbreviated to as 2-PSP(1,2)-min-2w). Our result improves the other known algorithm for this problem which has approximation ratio 11/7.

Ключевые слова: Traveling Salesman Problem, 2-Peripatetic Salesman Problem, polynomial algorithm, guaranteed approximation ratio.

Полный текст: PDF файл (859 kB)
Список литературы: PDF файл   HTML файл
Тип публикации: Статья
УДК: 519.712.3
MSC: 68W25
Поступила 29 августа 2011 г., опубликована 11 октября 2011 г.

Образец цитирования: А. Н. Глебов, А. В. Гордеева, Д. Ж. Замбалаева, “Алгоритм с оценкой 7/5 для задачи о двух коммивояжерах на минимум с различными весовыми функциями”, Сиб. электрон. матем. изв., 8 (2011), 296–309

Цитирование в формате AMSBIB
\RBibitem{GleGorZam11}
\by А.~Н.~Глебов, А.~В.~Гордеева, Д.~Ж.~Замбалаева
\paper Алгоритм с оценкой 7/5 для задачи о двух коммивояжерах на минимум с различными весовыми функциями
\jour Сиб. электрон. матем. изв.
\yr 2011
\vol 8
\pages 296--309
\mathnet{http://mi.mathnet.ru/semr325}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/semr325
  • http://mi.mathnet.ru/rus/semr/v8/p296

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