TY - GEN

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

AU - Eremeev, Anton V.

AU - Kelmanov, Alexander V.

AU - Pyatkin, Artem V.

AU - Ziegler, Igor A.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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.

AB - 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.

KW - Euclidean norm

KW - NP-hardness

KW - Pseudo-polymonial time

KW - Subset selection

KW - Vectors sum

KW - COMPLEXITY

UR - http://www.scopus.com/inward/record.url?scp=85039428182&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-73013-4_13

DO - 10.1007/978-3-319-73013-4_13

M3 - Conference contribution

AN - SCOPUS:85039428182

SN - 9783319730127

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 142

EP - 151

BT - Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers

A2 - VanDerAalst, WMP

A2 - Ignatov, DI

A2 - Khachay, M

A2 - Kuznetsov, SO

A2 - Lempitsky, null

A2 - Lomazova, IA

A2 - Loukachevitch, N

A2 - Napoli, A

A2 - Panchenko, A

A2 - Pardalos, PM

A2 - Savchenko, AV

A2 - Wasserman, S

PB - Springer-Verlag GmbH and Co. KG

T2 - 6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017

Y2 - 27 July 2017 through 29 July 2017

ER -