NP-трудность некоторых евклидовых задач разбиения конечного множества точек

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