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

Standard

Computational Complexity of the Choice Problem for Typical Representatives of a Finite Point Set in a Metric Space. / Борисова, Ирина Артемовна.

In: Journal of Applied and Industrial Mathematics, Vol. 19, No. 1, 1, 2025, p. 1-6.

Research output: Contribution to journal › Article › peer-review

BibTeX

@article{d99960fbc3d243c6ad2391af1465172f,

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

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. We prove that the problem under consideration is NP-hard by polynomially reducing the well-known NP-hard 3D-Matching problem to this one.",

keywords = "NP-ТРУДНАЯ ЗАДАЧА, ВЫБОР ТИПИЧНЫХ ПРЕДСТАВИТЕЛЕЙ, ФУНКЦИЯ КОНКУРЕНТНОГО СХОДСТВА, ЗАДАЧА О ТРЁХМЕРНОМ СОЧЕТАНИИ, МАШИННОЕ ОБУЧЕНИЕ, NP-HARD PROBLEM, CHOICE OF TYPICAL REPRESENTATIVES, FRIS-FUNCTION, 3D-MATCHING PROBLEM, MACHINE LEARNING",

author = "Борисова, {Ирина Артемовна}",

note = "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. – Vol. 19. - No. 1. – P. 1-6. – DOI 10.1134/S1990478925010016. – EDN IVZHWW. This research was supported by the Russian Foundation for Basic Research, project 17–01–00710.",

year = "2025",

doi = "10.1134/S1990478925010016",

language = "English",

volume = "19",

pages = "1--6",

journal = "Journal of Applied and Industrial Mathematics",

issn = "1990-4789",

publisher = "Maik Nauka-Interperiodica Publishing",

number = "1",

}

RIS

TY - JOUR

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

AU - Борисова, Ирина Артемовна

N1 - 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. – Vol. 19. - No. 1. – P. 1-6. – DOI 10.1134/S1990478925010016. – EDN IVZHWW. This research was supported by the Russian Foundation for Basic Research, project 17–01–00710.

PY - 2025

Y1 - 2025

N2 - 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.

AB - 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.

KW - NP-ТРУДНАЯ ЗАДАЧА

KW - ВЫБОР ТИПИЧНЫХ ПРЕДСТАВИТЕЛЕЙ

KW - ФУНКЦИЯ КОНКУРЕНТНОГО СХОДСТВА

KW - ЗАДАЧА О ТРЁХМЕРНОМ СОЧЕТАНИИ

KW - МАШИННОЕ ОБУЧЕНИЕ

KW - NP-HARD PROBLEM

KW - CHOICE OF TYPICAL REPRESENTATIVES

KW - FRIS-FUNCTION

KW - 3D-MATCHING PROBLEM

KW - MACHINE LEARNING

UR - https://www.scopus.com/pages/publications/105020675678

UR - https://www.elibrary.ru/item.asp?id=83155446

UR - https://www.elibrary.ru/item.asp?id=82904672

U2 - 10.1134/S1990478925010016

DO - 10.1134/S1990478925010016

M3 - Article

VL - 19

SP - 1

EP - 6

JO - Journal of Applied and Industrial Mathematics

JF - Journal of Applied and Industrial Mathematics

SN - 1990-4789

IS - 1

M1 - 1

ER -

ID: 72127122