1/2-Approximation polynomial-time algorithm for a problem of searching a subset

Alexander Ageev, Alexander Kel'Manov, Artem Pyatkin, Sergey Khamidullin, Vladimir Shenmaier

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

1 Цитирования (Scopus)

Аннотация

The work considers the mathematical aspects of one of the most fundamental problems of data analysis: search (choice) among a collection of objects for a subset of similar ones. In particular, the problem appears in connection with data editing and cleaning (removal of irrelevant (not similar) elements). We consider the model of this problem, i.e., the problem of searching for a subset of largest cardinality in a finite set of points of the Euclidean space for which quadratic variation of points with respect to its unknown centroid does not exceed a given fraction of the quadratic variation of points of the input set with respect to its centroid. It is proved that the problem is strongly NP-hard. A polynomial-time 1/2-approximation algorithm is proposed. The results of the numerical simulation demonstrating the effectiveness of the algorithm are presented.

Язык оригиналаанглийский
Название основной публикацииProceedings - 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017
ИздательInstitute of Electrical and Electronics Engineers Inc.
Страницы8-12
Число страниц5
ISBN (электронное издание)9781538615966
DOI
СостояниеОпубликовано - 14 ноя 2017
Событие2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017 - Novosibirsk, Российская Федерация
Продолжительность: 18 сен 201722 сен 2017

Конференция

Конференция2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017
СтранаРоссийская Федерация
ГородNovosibirsk
Период18.09.201722.09.2017

Fingerprint Подробные сведения о темах исследования «1/2-Approximation polynomial-time algorithm for a problem of searching a subset». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать