Полностью полиномиальная аппроксимационная схема для одной задачи двухкластерного разбиения последовательности

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