@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",

}