Standard

1/2-Approximation polynomial-time algorithm for a problem of searching a subset. / Ageev, Alexander; Kel'Manov, Alexander; Pyatkin, Artem et al.

Proceedings - 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017. Institute of Electrical and Electronics Engineers Inc., 2017. p. 8-12 8109827.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Ageev, A, Kel'Manov, A, Pyatkin, A, Khamidullin, S & Shenmaier, V 2017, 1/2-Approximation polynomial-time algorithm for a problem of searching a subset. in Proceedings - 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017., 8109827, Institute of Electrical and Electronics Engineers Inc., pp. 8-12, 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017, Novosibirsk, Russian Federation, 18.09.2017. https://doi.org/10.1109/SIBIRCON.2017.8109827

APA

Ageev, A., Kel'Manov, A., Pyatkin, A., Khamidullin, S., & Shenmaier, V. (2017). 1/2-Approximation polynomial-time algorithm for a problem of searching a subset. In Proceedings - 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017 (pp. 8-12). [8109827] Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SIBIRCON.2017.8109827

Vancouver

Ageev A, Kel'Manov A, Pyatkin A, Khamidullin S, Shenmaier V. 1/2-Approximation polynomial-time algorithm for a problem of searching a subset. In Proceedings - 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017. Institute of Electrical and Electronics Engineers Inc. 2017. p. 8-12. 8109827 doi: 10.1109/SIBIRCON.2017.8109827

Author

Ageev, Alexander ; Kel'Manov, Alexander ; Pyatkin, Artem et al. / 1/2-Approximation polynomial-time algorithm for a problem of searching a subset. Proceedings - 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017. Institute of Electrical and Electronics Engineers Inc., 2017. pp. 8-12

BibTeX

@inproceedings{1c4bd31ddc294f6799fc4194dc612d40,
title = "1/2-Approximation polynomial-time algorithm for a problem of searching a subset",
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 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.",
keywords = "Approximation algorithm, Computational complexity, Data mining, Machine learning, Minimal sum of squared distances, Optimization problems, Subset with the largest cardinality",
author = "Alexander Ageev and Alexander Kel'Manov and Artem Pyatkin and Sergey Khamidullin and Vladimir Shenmaier",
note = "Publisher Copyright: {\textcopyright} 2017 IEEE.; 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017 ; Conference date: 18-09-2017 Through 22-09-2017",
year = "2017",
month = nov,
day = "14",
doi = "10.1109/SIBIRCON.2017.8109827",
language = "English",
pages = "8--12",
booktitle = "Proceedings - 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
address = "United States",

}

RIS

TY - GEN

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

AU - Ageev, Alexander

AU - Kel'Manov, Alexander

AU - Pyatkin, Artem

AU - Khamidullin, Sergey

AU - Shenmaier, Vladimir

N1 - Publisher Copyright: © 2017 IEEE.

PY - 2017/11/14

Y1 - 2017/11/14

N2 - 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.

AB - 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.

KW - Approximation algorithm

KW - Computational complexity

KW - Data mining

KW - Machine learning

KW - Minimal sum of squared distances

KW - Optimization problems

KW - Subset with the largest cardinality

UR - http://www.scopus.com/inward/record.url?scp=85040528319&partnerID=8YFLogxK

U2 - 10.1109/SIBIRCON.2017.8109827

DO - 10.1109/SIBIRCON.2017.8109827

M3 - Conference contribution

AN - SCOPUS:85040528319

SP - 8

EP - 12

BT - Proceedings - 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON 2017

Y2 - 18 September 2017 through 22 September 2017

ER -

ID: 9112512