Geodesic
NP-hardness of~some data cleaning problem
Diskretnyj analiz i issledovanie operacij, Tome 28 (2021) no. 2, pp. 60-73

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

We prove the NP-hardness of the problem of outliers detection considered in this paper, to solving which a data analysis problem is reduced. As a quantitative assessment of the compactness of the image, the function of rival similarity (FRiS-function) is used, which evaluates the local similarity of objects with their closest neighbors. Illustr. 1, bibliogr. 23.
Keywords: NP-hardness, detecting outliers, image compactness, function of rival similarity. 
@article{DA_2021_28_2_a2,
     author = {O. A. Kutnenko and A. V. Plyasunov},
     title = {NP-hardness of~some data cleaning problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {60--73},
     publisher = {mathdoc},
     volume = {28},
     number = {2},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2021_28_2_a2/}
}
TY  - JOUR
AU  - O. A. Kutnenko
AU  - A. V. Plyasunov
TI  - NP-hardness of~some data cleaning problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2021
SP  - 60
EP  - 73
VL  - 28
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2021_28_2_a2/
LA  - ru
ID  - DA_2021_28_2_a2
ER  - 
%0 Journal Article
%A O. A. Kutnenko
%A A. V. Plyasunov
%T NP-hardness of~some data cleaning problem
%J Diskretnyj analiz i issledovanie operacij
%D 2021
%P 60-73
%V 28
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2021_28_2_a2/
%G ru
%F DA_2021_28_2_a2
O. A. Kutnenko; A. V. Plyasunov. NP-hardness of~some data cleaning problem. Diskretnyj analiz i issledovanie operacij, Tome 28 (2021) no. 2, pp. 60-73. http://geodesic.mathdoc.fr/item/DA_2021_28_2_a2/