Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
On complexity of searching a subset of vectors with shortest average under a cardinality restriction. / Eremeev, Anton V.; Kel’Manov, Alexander V.; Pyatkin, Artem V.
Analysis of Images, Social Networks and Texts - 5th International Conference, AIST 2016, Revised Selected Papers. ed. / DI Ignatov; MY Khachay; VG Labunets; N Loukachevitch; SI Nikolenko; A Panchenko; AV Savchenko; K Vorontsov. Springer-Verlag GmbH and Co. KG, 2017. p. 51-57 (Communications in Computer and Information Science; Vol. 661).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - On complexity of searching a subset of vectors with shortest average under a cardinality restriction
AU - Eremeev, Anton V.
AU - Kel’Manov, Alexander V.
AU - Pyatkin, Artem V.
PY - 2017/1/1
Y1 - 2017/1/1
N2 - In this paper, we study the computational complexity of the following subset search problem in a set of vectors. Given a set of N Euclidean q-dimensional vectors and an integer M, choose a subset of at least M vectors minimizing the Euclidean norm of the arithmetic mean of chosen vectors. This problem is induced, in particular, by a problem of clustering a set of points into two clusters where one of the clusters consists of points with a mean close to a given point. Without loss of generality the given point may be assumed to be the origin. We show that the considered problem is NP-hard in the strong sense and it does not admit any approximation algorithm with guaranteed performance, unless P = NP. An exact algorithm with pseudo-polynomial time complexity is proposed for the special case of the problem, where the dimension q of the space is bounded from above by a constant and the input data are integer.
AB - In this paper, we study the computational complexity of the following subset search problem in a set of vectors. Given a set of N Euclidean q-dimensional vectors and an integer M, choose a subset of at least M vectors minimizing the Euclidean norm of the arithmetic mean of chosen vectors. This problem is induced, in particular, by a problem of clustering a set of points into two clusters where one of the clusters consists of points with a mean close to a given point. Without loss of generality the given point may be assumed to be the origin. We show that the considered problem is NP-hard in the strong sense and it does not admit any approximation algorithm with guaranteed performance, unless P = NP. An exact algorithm with pseudo-polynomial time complexity is proposed for the special case of the problem, where the dimension q of the space is bounded from above by a constant and the input data are integer.
KW - Euclidean norm
KW - NP-hardness
KW - Pseudo-polymonial time
KW - Subset selection
KW - Vectors sum
KW - CLUSTER-ANALYSIS
UR - http://www.scopus.com/inward/record.url?scp=85014263432&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-52920-2_5
DO - 10.1007/978-3-319-52920-2_5
M3 - Conference contribution
AN - SCOPUS:85014263432
SN - 9783319529196
T3 - Communications in Computer and Information Science
SP - 51
EP - 57
BT - Analysis of Images, Social Networks and Texts - 5th International Conference, AIST 2016, Revised Selected Papers
A2 - Ignatov, DI
A2 - Khachay, MY
A2 - Labunets, VG
A2 - Loukachevitch, N
A2 - Nikolenko, SI
A2 - Panchenko, A
A2 - Savchenko, AV
A2 - Vorontsov, K
PB - Springer-Verlag GmbH and Co. KG
T2 - 5th International Conference on Analysis of Images, Social Networks and Texts, AIST 2016
Y2 - 6 April 2016 through 8 April 2016
ER -
ID: 10278115