Приближённый алгоритм для иерархической задачи о назначениях

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