On complexity of searching a subset of vectors with shortest average under a cardinality restriction

Anton V. Eremeev, Alexander V. Kel’Manov, Artem V. Pyatkin

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

2 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаанглийский
Название основной публикацииAnalysis of Images, Social Networks and Texts - 5th International Conference, AIST 2016, Revised Selected Papers
РедакторыDI Ignatov, MY Khachay, VG Labunets, N Loukachevitch, SI Nikolenko, A Panchenko, AV Savchenko, K Vorontsov
ИздательSpringer-Verlag GmbH and Co. KG
Страницы51-57
Число страниц7
ISBN (печатное издание)9783319529196
DOI
СостояниеОпубликовано - 1 янв 2017
Событие5th International Conference on Analysis of Images, Social Networks and Texts, AIST 2016 - Yekaterinburg, Российская Федерация
Продолжительность: 6 апр 20168 апр 2016

Серия публикаций

НазваниеCommunications in Computer and Information Science
Том661
ISSN (печатное издание)1865-0929

Конференция

Конференция5th International Conference on Analysis of Images, Social Networks and Texts, AIST 2016
СтранаРоссийская Федерация
ГородYekaterinburg
Период06.04.201608.04.2016

Fingerprint Подробные сведения о темах исследования «On complexity of searching a subset of vectors with shortest average under a cardinality restriction». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать