Standard
On finding maximum cardinality subset of vectors with a constraint on normalized squared length of vectors sum. / Eremeev, Anton V.; Kelmanov, Alexander V.; Pyatkin, Artem V. и др.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ред. / WMP VanDerAalst; DI Ignatov; M Khachay; SO Kuznetsov; Lempitsky; IA Lomazova; N Loukachevitch; A Napoli; A Panchenko; PM Pardalos; AV Savchenko; S Wasserman. Springer, 2018. стр. 142-151 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 10716 LNCS).
Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Harvard
Eremeev, AV, Kelmanov, AV
, Pyatkin, AV & Ziegler, IA 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 (ред.),
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Том. 10716 LNCS, Springer, стр. 142-151, 6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017, Moscow, Российская Федерация,
27.07.2017.
https://doi.org/10.1007/978-3-319-73013-4_13APA
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 (Ред.),
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (стр. 142-151). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 10716 LNCS). Springer.
https://doi.org/10.1007/978-3-319-73013-4_13Vancouver
Eremeev AV, Kelmanov AV
, Pyatkin AV, Ziegler IA.
On finding maximum cardinality subset of vectors with a constraint on normalized squared length of vectors sum. в VanDerAalst WMP, Ignatov DI, Khachay M, Kuznetsov SO, Lempitsky, Lomazova IA, Loukachevitch N, Napoli A, Panchenko A, Pardalos PM, Savchenko AV, Wasserman S, Редакторы, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer. 2018. стр. 142-151. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-73013-4_13
Author
Eremeev, Anton V. ; Kelmanov, Alexander V.
; Pyatkin, Artem V. и др. /
On finding maximum cardinality subset of vectors with a constraint on normalized squared length of vectors sum. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Редактор / WMP VanDerAalst ; DI Ignatov ; M Khachay ; SO Kuznetsov ; Lempitsky ; IA Lomazova ; N Loukachevitch ; A Napoli ; A Panchenko ; PM Pardalos ; AV Savchenko ; S Wasserman. Springer, 2018. стр. 142-151 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{8edd502b14944610b822b3925a1f0d46,
title = "On finding maximum cardinality subset of vectors with a constraint on normalized squared length of vectors sum",
abstract = "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{\textquoteright}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.",
keywords = "Euclidean norm, NP-hardness, Pseudo-polymonial time, Subset selection, Vectors sum, COMPLEXITY",
author = "Eremeev, {Anton V.} and Kelmanov, {Alexander V.} and Pyatkin, {Artem V.} and Ziegler, {Igor A.}",
year = "2018",
month = jan,
day = "1",
doi = "10.1007/978-3-319-73013-4_13",
language = "English",
isbn = "9783319730127",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "142--151",
editor = "WMP VanDerAalst and DI Ignatov and M Khachay and SO Kuznetsov and Lempitsky and IA Lomazova and N Loukachevitch and A Napoli and A Panchenko and PM Pardalos and AV Savchenko and S Wasserman",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
address = "United States",
note = "6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017 ; Conference date: 27-07-2017 Through 29-07-2017",
}
RIS
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
UR - https://www.mendeley.com/catalogue/26f62ef5-8903-38f8-adee-fe57ed28341f/
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 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
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
T2 - 6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017
Y2 - 27 July 2017 through 29 July 2017
ER -
