Computational Complexity of the Choice Problem for Typical Representatives of a Finite Point Set in a Metric Space

Computational Complexity of the Choice Problem for Typical Representatives of a Finite Point Set in a Metric Space Full article

Journal

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

Output data

Year: 2025, Volume: 19, Number: 1, Pages: 1-6 Pages count : 6 DOI: 10.1134/S1990478925010016

Funding (1)

Russian Foundation for Basic Research

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

Submitted:	Sep 3, 2024
Accepted:	Sep 22, 2024
Published print:	Nov 2, 2025
Published online:	Nov 2, 2025

Scopus:	2-s2.0-105020675678
Elibrary:	83155446

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