Том 17, номер 4, 2010 г., Стр. 84-91

УДК 519.176
Шенмайер В. В.
Асимптотически точный алгоритм для задачи коммивояжёра на максимум в конечномерном нормированном пространстве

Аннотация:
Рассматривается геометрическая задача коммивояжёра на максимум. Предполагается, что вершинами графа являются точки в произвольном конечномерном нормированном пространстве. Для данной задачи получен приближённый алгоритм с относительной погрешностью, стремящейся к нулю с ростом числа вершин. Алгоритм является обобщением известного алгоритма А. И. Сердюкова для евклидовой задачи MAX TSP.
Ил. 4, библиогр. 6.

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

Шенмайер Владимир Владимирович ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: shenmaier@mail.ru

Статья поступила 28 декабря 2009 г.
Исправленный вариант — 6 марта 2010 г.