Полиномиальная разрешимость одномерного случая одной NP-трудной задачи кластеризации

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