Том 15, номер 4, 2008 г., Стр. 84-91

УДК 519.176
В. В. Шенмайер
Приближённый алгоритм для иерархической задачи о назначениях

Аннотация:
Иерархическая задача о назначениях заключается в отыскании иерархической последовательности решений задачи о $k$-медиане возрастающей мощности. Лучший известный алгоритм для данной задачи в общем метрическом случае имеет относительную оценку точности 20,71. Рассмотрен случай, когда клиенты и предприятия расположены в точках вещественной прямой, а также случай евклидова пространства. Предлагается алгоритм c точностью, равной 8 в случае вещественной прямой и $8+4\sqrt2$ (приблизительно 13,66) – в евклидовом случае.
Библиогр. 6.

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

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

Статья поступила 18 декабря 2007 г.
Исправленный вариант — 11 июля 2008 г.