NP-Hardness of Some Data Cleaning Problem
Olga A. Kutnenko, A. V. Plyasunov · Journal of Applied and Industrial Mathematics · 2021
Abstract We prove the NP-hardness of the data cleaning problem under study. One of the data analysis questions reduces to the problem. As a quantitative assessment of the image compactness, we use the function of rival similarity (FRiS-function) by which we evaluate the local similarity of objects with their closest neighbors.