Вычислительная сложность задачи выбора типичных представителей конечного множества точек метрического пространства Full article
| Journal |
Дискретный анализ и исследование операций
ISSN: 1560-7542 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2025, Volume: 32, Number: 1, Pages: 5–15 Pages count : 11 DOI: 10.33048/daio.2025.32.812 | ||||
| Tags | NP-трудная задача, выбор типичных представителей, функция конкурентного сходства, задача о трёхмерном сочетании, машинное обучение. | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (1)
| 1 | Russian Foundation for Basic Research | 17-01-00710 |
Abstract:
В работе исследуется сложностной статус одной экстремальной задачи выбора подмножества p наиболее типичных точек в заданном конечном множества точек метрического пространства. При этом требуется, чтобы выбранное подмножество наилучшим образом описывало исходное множества с точки зрения некоторого геометрического критерия. Рассматриваемая задача является формализацией одной прикладной проблемы из анализа данных, заключающейся в отыскании подмножества типичных представителей выборки с опорой на функцию конкурентного сходства. В статье доказывается, что рассматриваемая задача является NP-трудной. Для этого к ней полиномиально сводится одна из NP-трудных задач - задача о трехмерном сочетании.
Cite:
Борисова И.А.
Вычислительная сложность задачи выбора типичных представителей конечного множества точек метрического пространства
Дискретный анализ и исследование операций. 2025. Т.32. №1. С.5–15. DOI: 10.33048/daio.2025.32.812
Вычислительная сложность задачи выбора типичных представителей конечного множества точек метрического пространства
Дискретный анализ и исследование операций. 2025. Т.32. №1. С.5–15. DOI: 10.33048/daio.2025.32.812
Dates:
| Submitted: | Sep 3, 2024 |
| Accepted: | Sep 22, 2024 |
| Published print: | Mar 20, 2025 |
| Published online: | Mar 20, 2025 |
Identifiers:
No identifiers
Citing:
Пока нет цитирований