Computational complexity of the choice problem for typical representatives of a finite point set in a metric space

I. A. Borisova<sup>ab

a</sup> Sobolev Institute of Mathematics, 4 Acad. Koptyug Avenue, 630090 Novosibirsk, Russia
^b Novosibirsk State University, 2 Pirogov Street, 630090 Novosibirsk, Russia

Abstract: 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 of. We prove that the problem under consideration is NP-hard by polynomially reducing the well-known NP-hard 3D-Matching problem to this one. Illustr. 1, bibliogr. 14.

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

UDC: 519.254

Received: 03.09.2024
Revised: 16.09.2024
Accepted: 22.09.2024

DOI: 10.33048/daio.2025.32.812

 English version: Journal of Applied and Industrial Mathematics, 2025, 19:1, 1–6