20, №1 УДК 519.2+621.391 О псевдополиномиальной разрешимости квадратичной евклидовой задачи поиска семейства непересекающихся подмножеств∗ А. <...> О псевдополиномиальной разрешимости квадратичной евклидовой задачи поиска семейства непересекающихся подмножеств // Сиб. журн. вычисл. математики / РАН. <...> Рассматривается NP-трудная в сильном смысле задача поиска в конечном множестве точек евклидова пространства семейства непересекающихся подмножеств, имеющих заданные мощности. <...> Критерием решения задачи является минимум суммы по всем подмножествам сумм квадратов расстояний от элементов подмножеств до их геометрических центров. <...> Доказано, что задача разрешима за псевдополиномиальное время, если координаты входных точек целочисленны, а размерность пространства и число искомых подмножеств фиксированы (ограничены константами). <...> DOI: 10.15372/SJNM20170102 Ключевые слова: поиск подмножеств, кластерный анализ, евклидово пространство, минимум суммы квадратов расстояний, NP-трудная задача, точный псевдополинимиальный алгоритм. <...> On pseudopolynomial-time solvability of a quadratic Euclidean problem of finding a family of disjoint subsets // Siberian J. <...> We consider a strongly NP-hard problem of finding a family of disjoint subsets with given cardinalities in a finite set of points from the Euclidean space. <...> A minimum of the sum over all required subsets of the sum of the squared distances from the elements of these subsets to their geometric centers is used as a search criterion.We have proved that if the coordinates of the input points are integer, and the space dimension and the number of required subsets are fixed (i.e. bounded by some constants), then the problem is a pseudopolynomial-time solvable one. <...> Введение Предметом исследования настоящей работы является одна из NP-трудных в сильном смысле задач поиска семейства непересекающихся подмножеств в конечном множестве точек евклидова пространства. <...> 20, №1 Исследование мотивировано слабой изученностью задачи в алгоритмическом плане. <...> Поиск подклассов NP-трудных в сильном смысле задач, для которых точные псевдополиномиальные алгоритмы <...>