Standard

NP-Hardness of Some Data Cleaning Problem. / Kutnenko, O. A.; Plyasunov, A. V.

In: Journal of Applied and Industrial Mathematics, Vol. 15, No. 2, 04.2021, p. 285-291.

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

Harvard

Kutnenko, OA & Plyasunov, AV 2021, 'NP-Hardness of Some Data Cleaning Problem', Journal of Applied and Industrial Mathematics, vol. 15, no. 2, pp. 285-291. https://doi.org/10.1134/S1990478921020095

APA

Kutnenko, O. A., & Plyasunov, A. V. (2021). NP-Hardness of Some Data Cleaning Problem. Journal of Applied and Industrial Mathematics, 15(2), 285-291. https://doi.org/10.1134/S1990478921020095

Vancouver

Kutnenko OA, Plyasunov AV. NP-Hardness of Some Data Cleaning Problem. Journal of Applied and Industrial Mathematics. 2021 Apr;15(2):285-291. doi: 10.1134/S1990478921020095

Author

Kutnenko, O. A. ; Plyasunov, A. V. / NP-Hardness of Some Data Cleaning Problem. In: Journal of Applied and Industrial Mathematics. 2021 ; Vol. 15, No. 2. pp. 285-291.

BibTeX

@article{7b4c6285500040cf91c9018d4cd8fd81,
title = "NP-Hardness of Some Data Cleaning Problem",
abstract = "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.",
keywords = "data cleaning, function of rival similarity, image compactness, NP-hardness",
author = "Kutnenko, {O. A.} and Plyasunov, {A. V.}",
note = "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: {\textcopyright} 2021, Pleiades Publishing, Ltd.",
year = "2021",
month = apr,
doi = "10.1134/S1990478921020095",
language = "English",
volume = "15",
pages = "285--291",
journal = "Journal of Applied and Industrial Mathematics",
issn = "1990-4789",
publisher = "Maik Nauka-Interperiodica Publishing",
number = "2",

}

RIS

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 -

ID: 34376897