О сложности некоторых максиминных задач кластеризации

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