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

Cite: Борисова И.А.
Вычислительная сложность задачи выбора типичных представителей конечного множества точек метрического пространства
Дискретный анализ и исследование операций. 2025. Т.32. №1. С.5–15. DOI: 10.33048/daio.2025.32.812 РИНЦ

Translated: Borisova I.A.
Computational Complexity of the Choice Problem for Typical Representatives of a Finite Point Set in a Metric Space
Journal of Applied and Industrial Mathematics. 2025. V.19. N1. P.1-6. DOI: 10.1134/S1990478925010016 Scopus РИНЦ

Dates:

Submitted:	Sep 3, 2024
Accepted:	Sep 22, 2024
Published print:	Mar 20, 2025
Published online:	Mar 20, 2025

Identifiers:

Elibrary:

82904672

Citing: Пока нет цитирований

Altmetrics: