NP-Hardness of Some Data Cleaning Problem

Research output: Contribution to journalArticlepeer-review

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.

Translated title of the contributionNP-трудность некоторой задачи цензурирования данных
Original languageEnglish
Pages (from-to)285-291
Number of pages7
JournalJournal of Applied and Industrial Mathematics
Volume15
Issue number2
DOIs
Publication statusPublished - Apr 2021

Keywords

  • data cleaning
  • function of rival similarity
  • image compactness
  • NP-hardness

OECD FOS+WOS

  • 1.01 MATHEMATICS

Fingerprint

Dive into the research topics of 'NP-Hardness of Some Data Cleaning Problem'. Together they form a unique fingerprint.

Cite this