Approximation polynomial algorithm for the data editing and data cleaning problem

A. A. Ageeva, A. V. Kel’manov, A. V. Pyatkin, S. A. Khamidullin, V. V. Shenmaier

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)

Abstract

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 maximal 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 1/2-approximation algorithm is proposed. The results of the numerical simulation demonstrating the effectiveness of the algorithm are presented.

Original languageEnglish
Pages (from-to)365-370
Number of pages6
JournalPattern Recognition and Image Analysis
Volume27
Issue number3
DOIs
Publication statusPublished - 1 Jul 2017

Keywords

  • data analysis
  • Euclidean space
  • maximal cardinality
  • NP-hard problem
  • polynomial approximation algorithm
  • square variation
  • subset of similar elements

Fingerprint

Dive into the research topics of 'Approximation polynomial algorithm for the data editing and data cleaning problem'. Together they form a unique fingerprint.

Cite this