@inproceedings{3dc6f0601ac84f1abeeb96c3d86e885c,
title = "On complexity of searching a subset of vectors with shortest average under a cardinality restriction",
abstract = "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.",
keywords = "Euclidean norm, NP-hardness, Pseudo-polymonial time, Subset selection, Vectors sum, CLUSTER-ANALYSIS",
author = "Eremeev, {Anton V.} and Kel{\textquoteright}Manov, {Alexander V.} and Pyatkin, {Artem V.}",
year = "2017",
month = jan,
day = "1",
doi = "10.1007/978-3-319-52920-2_5",
language = "English",
isbn = "9783319529196",
series = "Communications in Computer and Information Science",
publisher = "Springer-Verlag GmbH and Co. KG",
pages = "51--57",
editor = "DI Ignatov and MY Khachay and VG Labunets and N Loukachevitch and SI Nikolenko and A Panchenko and AV Savchenko and K Vorontsov",
booktitle = "Analysis of Images, Social Networks and Texts - 5th International Conference, AIST 2016, Revised Selected Papers",
address = "Germany",
note = "5th International Conference on Analysis of Images, Social Networks and Texts, AIST 2016 ; Conference date: 06-04-2016 Through 08-04-2016",
}