Computational Complexity of the Choice Problem for Typical Representatives of a Finite Point Set in a Metric Space | Sciact - Система учета научной деятельности ИМ СО РАН

Computational Complexity of the Choice Problem for Typical Representatives of a Finite Point Set in a Metric Space Научная публикация

Журнал

Journal of Applied and Industrial Mathematics
ISSN: 1990-4789 , E-ISSN: 1990-4797

Вых. Данные

Год: 2025, Том: 19, Номер: 1, Страницы: 1-6 Страниц : 6 DOI: 10.1134/S1990478925010016

Ключевые слова

NP-hard problem, choice of typical representatives, FRiS-function, 3D-matching problem, machine learning

Авторы

Borisova I.A. ^1,2

Организации

1	Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, Novosibirsk, 630090, Russia
2	Novosibirsk State University, Novosibirsk, 630090, Russia

Информация о финансировании (1)

Российский фонд фундаментальных исследований

17-01-00710

We analyze the complexity of one extremal problem of choosing a subset of p points in a given finite set in a metric space. The chosen subset of points is required to describe given clusters in the best way from the point of view of some geometric criterion. This problem is a formalization of one applied problem from data mining that consists in finding a subset of typical representatives of a dataset based on the rival similarity function. We prove that the problem under consideration is NP-hard by polynomially reducing the well-known NP-hard 3D-Matching problem to this one.

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 РИНЦ

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

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

Scopus:	2-s2.0-105020675678
РИНЦ:	83155446

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