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

Рассматриваются задачи двухкластерного разбиения конечного множества точек евклидова пространства. В этих задачах минимизируются следующие критерии: (1) сумма по обоим кластерам суммы квадратов попарных расстояний между элементами кластера, (2) сумма умноженных на мощность кластеров сумм квадратов расстояний от элементов кластера до его геометрического центра. Под геометрическим центром кластера (центроидом) понимается точка пространства, равная среднему значению элементов кластера. Кроме того, рассматривается близкая к (2) в постановочном плане задача, в которой на входе задан желаемый центр одного из кластеров, а центр другого, как и в задаче (2), неизвестен (является оптимизируемой переменной). Анализируются варианты задач, в которых мощности кластеров: (1) заданы на входе, (2) неизвестны. Установлено, что все рассмотренные задачи NP-трудны в сильном смысле и для общего случая этих задач не существует полностью полиномиальной приближенной схемы (FPTAS), если $\mathrm{P\ne NP}$. Библ. 21.