Псевдополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подмножества векторов и кластерного анализа

Анализируются некоторые $NP$-трудные задачи кластеризации и поиска в заданном множестве векторов евклидова пространства подмножества векторов фиксированной мощности. К этим задачам сводится одна из актуальных проблем анализа данных по критерию минимума суммы квадратов. Обоснованы псевдополиномиальные алгоритмы, гарантирующие отыскание оптимума этих задач в случае, когда компоненты векторов имеют целочисленные значения и размерность пространства фиксирована.

Статья представлена к публикации членом редколлегии: А. И. Кибзун