Computational Complexity of the Problem of Choosing Typical Representatives in a 2-Clustering of a Finite Set of Points in a Metric Space

Standard

Computational Complexity of the Problem of Choosing Typical Representatives in a 2-Clustering of a Finite Set of Points in a Metric Space. / Borisova, I. A.

In: Journal of Applied and Industrial Mathematics, Vol. 14, No. 2, 01.05.2020, p. 242-248.

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

BibTeX

@article{775ba062047c4ff19ca1305bc97cd99f,

title = "Computational Complexity of the Problem of Choosing Typical Representatives in a 2-Clustering of a Finite Set of Points in a Metric Space",

abstract = "We consider the computational complexity of one extremal problem of choosing a subsetof p points from some given 2-clustering of a finite set in a metric space. Thechosen subset of points has to describe the given clusters in the best way from the viewpoint ofsome geometric criterion. This is a formalization of an applied problem of data mining whichconsists in finding a subset of typical representatives of a dataset composed of two classes basedon the function of rival similarity. The problem is proved to be NP-hard. To this end, wepolynomially reduce to the problem one of the well-known problems NP-hard in the strong sense,the p-median problem.",

keywords = "data mining, NP-hard problem, p-median problem, rival similarity, typical representative",

author = "Borisova, {I. A.}",

year = "2020",

month = may,

day = "1",

doi = "10.1134/S1990478920020039",

language = "English",

volume = "14",

pages = "242--248",

journal = "Journal of Applied and Industrial Mathematics",

issn = "1990-4789",

publisher = "Maik Nauka-Interperiodica Publishing",

number = "2",

}

RIS

TY - JOUR

T1 - Computational Complexity of the Problem of Choosing Typical Representatives in a 2-Clustering of a Finite Set of Points in a Metric Space

AU - Borisova, I. A.

PY - 2020/5/1

Y1 - 2020/5/1

N2 - We consider the computational complexity of one extremal problem of choosing a subsetof p points from some given 2-clustering of a finite set in a metric space. Thechosen subset of points has to describe the given clusters in the best way from the viewpoint ofsome geometric criterion. This is a formalization of an applied problem of data mining whichconsists in finding a subset of typical representatives of a dataset composed of two classes basedon the function of rival similarity. The problem is proved to be NP-hard. To this end, wepolynomially reduce to the problem one of the well-known problems NP-hard in the strong sense,the p-median problem.

AB - We consider the computational complexity of one extremal problem of choosing a subsetof p points from some given 2-clustering of a finite set in a metric space. Thechosen subset of points has to describe the given clusters in the best way from the viewpoint ofsome geometric criterion. This is a formalization of an applied problem of data mining whichconsists in finding a subset of typical representatives of a dataset composed of two classes basedon the function of rival similarity. The problem is proved to be NP-hard. To this end, wepolynomially reduce to the problem one of the well-known problems NP-hard in the strong sense,the p-median problem.

KW - data mining

KW - NP-hard problem

KW - p-median problem

KW - rival similarity

KW - typical representative

UR - http://www.scopus.com/inward/record.url?scp=85087793102&partnerID=8YFLogxK

U2 - 10.1134/S1990478920020039

DO - 10.1134/S1990478920020039

M3 - Article

AN - SCOPUS:85087793102

VL - 14

SP - 242

EP - 248

JO - Journal of Applied and Industrial Mathematics

JF - Journal of Applied and Industrial Mathematics

SN - 1990-4789

IS - 2

ER -

ID: 24769429