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

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

Переводная: 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 РИНЦ

Даты:

Поступила в редакцию:	3 сент. 2024 г.
Принята к публикации:	22 сент. 2024 г.
Опубликована в печати:	20 мар. 2025 г.
Опубликована online:	20 мар. 2025 г.

Идентификаторы БД:

РИНЦ:

82904672

Цитирование в БД: Пока нет цитирований

Альметрики: