NР-ПОЛНОТА НЕКОТОРЫХ ЗАДАЧ ВЫБОРАПОДМНОЖЕСТВА ВЕКТОРОВ

摘要

Доказана NР-полнота некоторых задач выбора под-множества векторов евклидова пространства. К решению таких за-дач сводится одна из проблем анализа данных. Предполагается, чтоискомое подмножество имеет фиксированную мощность и Включает векторы, близкие между собой по критерию минимума суммыквадратов расстояний.