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

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

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


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




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

Сибирские электронные математические известия, 2011, том 8, страницы 296–309 (Mi semr325)  
Эта публикация цитируется в 5 научных статьях (всего в 5 статьях)

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

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

a Институт математики им. С.~Л.~Соболева СО РАН, пр. академика Коптюга 4, 630090, Новосибирск, Россия
b Новосибирский государственный университет, ул. Пирогова 2, 630090, Новосибирск, Россия
PDF полного текста (859 kB) Список цитирования (5)
Список литературы:
PDF
HTML
Аннотация: 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.
Поступила 29 августа 2011 г., опубликована 11 октября 2011 г.
Тип публикации: Статья
УДК: 519.712.3
MSC: 68W25
Образец цитирования: А. Н. Глебов, А. В. Гордеева, Д. Ж. Замбалаева, “Алгоритм с оценкой 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}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/semr325
  • https://www.mathnet.ru/rus/semr/v8/p296
    • Эта публикация цитируется в следующих 5 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024