On finding maximum cardinality subset of vectors with a constraint on normalized squared length of vectors sum

Anton V. Eremeev, Alexander V. Kelmanov, Artem V. Pyatkin, Igor A. Ziegler

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

Аннотация

In this paper, we consider the problem of finding a maximum cardinality subset of vectors, given a constraint on the normalized squared length of vectors sum. This problem is closely related to Problem 1 from (Eremeev, Kel’manov, Pyatkin, 2016). The main difference consists in swapping the constraint with the optimization criterion. We prove that the problem is NP-hard even in terms of finding a feasible solution. An exact algorithm for solving this problem is proposed. The algorithm has a pseudo-polynomial time complexity in the special case of the problem, where the dimension of the space is bounded from above by a constant and the input data are integer. A computational experiment is carried out, where the proposed algorithm is compared to COINBONMIN solver, applied to a mixed integer quadratic programming formulation of the problem. The results of the experiment indicate superiority of the proposed algorithm when the dimension of Euclidean space is low, while the COINBONMIN has an advantage for larger dimensions.

Язык оригиналаанглийский
Название основной публикацииAnalysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers
РедакторыWMP VanDerAalst, DI Ignatov, M Khachay, SO Kuznetsov, Lempitsky, IA Lomazova, N Loukachevitch, A Napoli, A Panchenko, PM Pardalos, AV Savchenko, S Wasserman
ИздательSpringer-Verlag GmbH and Co. KG
Страницы142-151
Число страниц10
ISBN (печатное издание)9783319730127
DOI
СостояниеОпубликовано - 1 янв 2018
Событие6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017 - Moscow, Российская Федерация
Продолжительность: 27 июл 201729 июл 2017

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

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том10716 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

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

Fingerprint Подробные сведения о темах исследования «On finding maximum cardinality subset of vectors with a constraint on normalized squared length of vectors sum». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Eremeev, A. V., Kelmanov, A. V., Pyatkin, A. V., & Ziegler, I. A. (2018). On finding maximum cardinality subset of vectors with a constraint on normalized squared length of vectors sum. В WMP. VanDerAalst, DI. Ignatov, M. Khachay, SO. Kuznetsov, Lempitsky, IA. Lomazova, N. Loukachevitch, A. Napoli, A. Panchenko, PM. Pardalos, AV. Savchenko, & S. Wasserman (Ред.), Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers (стр. 142-151). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 10716 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-319-73013-4_13