Geodesic
Computational complexity of the problem of~choosing typical representatives in~a~2-clustering of a~finite set of~points in~a~metric~space
Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 2, pp. 5-16

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider the computational complexity of one extremal problem of choosing a subset of $p$ points from some given $2$-clustering of a finite set in a metric space. The chosen subset of points has to describe the given clusters in the best way from the viewpoint of some geometric criterion. This is a formalization of an applied problem of data mining which consists in finding a subset of typical representatives of a dataset composed of two classes based on the function of rival similarity. The problem is proved to be NP-hard. To this end, we polynomially reduce to the problem one of the well-known problems NP-hard in the strong sense, the $p$-median problem. Bibliogr. 15.
Keywords: NP-hard problem, typical representative, rival similarity, $p$-median problem, data mining. 
@article{DA_2020_27_2_a0,
     author = {I. A. Borisova},
     title = {Computational complexity of the problem of~choosing typical representatives in~a~2-clustering of a~finite set of~points in~a~metric~space},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {5--16},
     publisher = {mathdoc},
     volume = {27},
     number = {2},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2020_27_2_a0/}
}
TY  - JOUR
AU  - I. A. Borisova
TI  - Computational complexity of the problem of~choosing typical representatives in~a~2-clustering of a~finite set of~points in~a~metric~space
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2020
SP  - 5
EP  - 16
VL  - 27
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2020_27_2_a0/
LA  - ru
ID  - DA_2020_27_2_a0
ER  - 
%0 Journal Article
%A I. A. Borisova
%T Computational complexity of the problem of~choosing typical representatives in~a~2-clustering of a~finite set of~points in~a~metric~space
%J Diskretnyj analiz i issledovanie operacij
%D 2020
%P 5-16
%V 27
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2020_27_2_a0/
%G ru
%F DA_2020_27_2_a0
I. A. Borisova. Computational complexity of the problem of~choosing typical representatives in~a~2-clustering of a~finite set of~points in~a~metric~space. Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 2, pp. 5-16. http://geodesic.mathdoc.fr/item/DA_2020_27_2_a0/