Open AccessON FINDING MINIMUM CARDINALITY SUBSET OF VECTORS WITH A CONSTRAINT ON THE SUM OF SQUARED EUCLIDEAN PAIRWISE DISTANCES
Author(s) -
A. V. Eremeev,
M. Ya. Kovalyov,
A. V. Pyatkin
Publication year - 2021
Publication title -
dinamika sistem, mehanizmov i mašin
Language(s) - Russian
Resource type - Journals
ISSN - 2310-9793
DOI - 10.25206/2310-9793-9-4-17-19
Subject(s) - cardinality (data modeling) , pairwise comparison , euclidean distance , constraint (computer aided design) , combinatorics , euclidean geometry , mathematics , square (algebra) , discrete mathematics , computer science , statistics , geometry , data mining
В рассматриваемой задаче требуется из конечного множества точек (векторов) евклидова пространства выбрать подмножество минимальной мощности при ограничении снизуна сумму квадратов евклидовых расстояний между всеми точками выбранного подмножества. Задача тесно связана с хорошо известной задачей максимального разнообразия. Доказано, что рассматриваемая задача NP-трудна в сильном смысле и предложен точный алгоритм ее решения в случае целочисленных входных данных. Алгоритм имеет псевдополиномиальную временную сложность в частном случае, когда размерность пространства ограничена сверху константой, а входные данные целочисленные.