О сложности некоторых задач кластерного анализа векторных последовательностей

Доказана NP-полнота двух задач кластеризации (разбиения) конечной последовательности векторов евклидова пространства. В оптимизационных вариантах обеих задач требуется разбить элементы последовательности на фиксированное число кластеров по критерию минимума суммы квадратов расстояний от элементов кластеров до их центров. В одной из задач мощности кластеров заданы на входе задачи, а в другой неизвестны (являются оптимизируемыми величинами). За исключением центра одного (специального кластера) центры остальных кластеров определяются как средние значения по всем векторам, образующим эти кластеры. Центр специального кластера полагается равным нулю. При этом разбиение подчинено условию: для всех векторов, не входящих в специальный кластер, разность между номерами последующего и предыдущего векторов, входящих в любой из этих кластеров, ограничена сверху и снизу заданными константами. Библиогр. 20.