Точный псевдополиномиальный алгоритм для одной задачи разбиения последовательности

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