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

Эта публикация цитируется в 5 статьях

Алгоритм с оценкой 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.

УДК: 519.712.3

MSC: 68W25

Поступила 29 августа 2011 г., опубликована 11 октября 2011 г.