NP-Hardness of Some Data Cleaning Problem

O. A. Kutnenko; A. V. Plyasunov

doi:10.1134/S1990478921020095

NP-Hardness of Some Data Cleaning Problem

Переведенное название: NP-трудность некоторой задачи цензурирования данных

O. A. Kutnenko, A. V. Plyasunov

Результат исследования: Научные публикации в периодических изданиях › статья › рецензирование

Аннотация

Доказана NP-трудность рассматриваемой в работе постановки задачи цензурирования данных. К решению такой задачи сводится одна из проблем анализа данных. В качестве количественной оценки компактности образа используется функция конкурентного сходства (FRiS-функция), с помощью которой оценивается локальное сходство объектов со своими ближайшими соседями. Ил. 1, библиогр. 23.

Переведенное название	NP-трудность некоторой задачи цензурирования данных
Язык оригинала	английский
Страницы (с-по)	285-291
Число страниц	7
Журнал	Journal of Applied and Industrial Mathematics
Том	15
Номер выпуска	2
DOI	https://doi.org/10.1134/S1990478921020095
Состояние	Опубликовано - апр. 2021

Предметные области OECD FOS+WOS

1.01 МАТЕМАТИКА

Доступ к документу

10.1134/S1990478921020095

Другие файлы и ссылки

Ссылка на публикацию в Scopus

Fingerprint

Подробные сведения о темах исследования «NP-трудность некоторой задачи цензурирования данных». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать

@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",

}

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 -