Вычислительная сложность задачи выбора типичных представителей в 2-разбиении конечного множества точек метрического пространства

Исследуется вычислительная сложность одной экстремальной задачи выбора подмножества $p$ точек в заданном 2-разбиении конечного множества точек метрического пространства. При этом требуется, чтобы выбранное подмножество наилучшим образом описывало определяемые 2-разбиением кластеры с точки зрения некоторого геометрического критерия. Рассматриваемая задача является формализацией одной прикладной проблемы из анализа данных, заключающейся в отыскании подмножества типичных представителей выборки, состоящей из объектов двух классов с опорой на функцию конкурентного сходства. В статье доказывается, что рассматриваемая задача NP-трудна. Для этого к ней полиномиально сводится одна из хорошо известных NP-трудных в сильном смысле задач — задача о $p$-медиане. Библиогр. 15.