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

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

Даты:

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

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

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

Альметрики: