TY - JOUR

T1 - NP-Hardness of Some Data Cleaning Problem

AU - Kutnenko, O. A.

AU - Plyasunov, A. V.

N1 - Funding Information: The authors were supported by the State Task to the Sobolev Institute of Mathematics (projects nos. 0314–2019–0015 and 0314–2019–0014). Publisher Copyright: © 2021, Pleiades Publishing, Ltd.

PY - 2021/4

Y1 - 2021/4

N2 - We prove the NP-hardness of the data cleaning problem under study. One of the dataanalysis questions reduces to the problem. As a quantitative assessment of the imagecompactness, we use the function of rival similarity (FRiS-function) by which we evaluate thelocal similarity of objects with their closest neighbors.

AB - We prove the NP-hardness of the data cleaning problem under study. One of the dataanalysis questions reduces to the problem. As a quantitative assessment of the imagecompactness, we use the function of rival similarity (FRiS-function) by which we evaluate thelocal similarity of objects with their closest neighbors.

KW - data cleaning

KW - function of rival similarity

KW - image compactness

KW - NP-hardness

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

U2 - 10.1134/S1990478921020095

DO - 10.1134/S1990478921020095

M3 - Article

AN - SCOPUS:85116188441

VL - 15

SP - 285

EP - 291

JO - Journal of Applied and Industrial Mathematics

JF - Journal of Applied and Industrial Mathematics

SN - 1990-4789

IS - 2

ER -