Standard

On finding minimum cardinality subset of vectors with a constraint on the sum of squared euclidean pairwise distances. / Eremeev, Anton V.; Kovalyov, Mikhail Y.; Pyatkin, Artem V.

Learning and Intelligent Optimization - 14th International Conference, LION 14, 2020, Revised Selected Papers. ed. / Ilias S. Kotsireas; Panos M. Pardalos. Springer Gabler, 2020. p. 40-45 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12096 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Eremeev, AV, Kovalyov, MY & Pyatkin, AV 2020, On finding minimum cardinality subset of vectors with a constraint on the sum of squared euclidean pairwise distances. in IS Kotsireas & PM Pardalos (eds), Learning and Intelligent Optimization - 14th International Conference, LION 14, 2020, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12096 LNCS, Springer Gabler, pp. 40-45, 14th International Conference on Learning and Intelligent Optimization, LION 2020, Athens, Greece, 24.05.2020. https://doi.org/10.1007/978-3-030-53552-0_6

APA

Eremeev, A. V., Kovalyov, M. Y., & Pyatkin, A. V. (2020). On finding minimum cardinality subset of vectors with a constraint on the sum of squared euclidean pairwise distances. In I. S. Kotsireas, & P. M. Pardalos (Eds.), Learning and Intelligent Optimization - 14th International Conference, LION 14, 2020, Revised Selected Papers (pp. 40-45). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12096 LNCS). Springer Gabler. https://doi.org/10.1007/978-3-030-53552-0_6

Vancouver

Eremeev AV, Kovalyov MY, Pyatkin AV. On finding minimum cardinality subset of vectors with a constraint on the sum of squared euclidean pairwise distances. In Kotsireas IS, Pardalos PM, editors, Learning and Intelligent Optimization - 14th International Conference, LION 14, 2020, Revised Selected Papers. Springer Gabler. 2020. p. 40-45. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-53552-0_6

Author

Eremeev, Anton V. ; Kovalyov, Mikhail Y. ; Pyatkin, Artem V. / On finding minimum cardinality subset of vectors with a constraint on the sum of squared euclidean pairwise distances. Learning and Intelligent Optimization - 14th International Conference, LION 14, 2020, Revised Selected Papers. editor / Ilias S. Kotsireas ; Panos M. Pardalos. Springer Gabler, 2020. pp. 40-45 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{b192b4491d9f4282a92fc1c9fe63d78e,
title = "On finding minimum cardinality subset of vectors with a constraint on the sum of squared euclidean pairwise distances",
abstract = "In this paper, we consider the problem of finding a minimum cardinality subset of vectors, given a constraint on the sum of squared Euclidean distances between all vectors of the chosen subset. This problem is closely related to the well-known Maximum Diversity Problem. The main difference consists in swapping the constraint with the optimization criterion. We prove that the problem is NP-hard in the strong sense. 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.",
keywords = "Euclidean space, Exact algorithm, Integer instance, NP-hardness, Pseudo-polynomial time, Subset of points",
author = "Eremeev, {Anton V.} and Kovalyov, {Mikhail Y.} and Pyatkin, {Artem V.}",
note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2020.; 14th International Conference on Learning and Intelligent Optimization, LION 2020 ; Conference date: 24-05-2020 Through 28-05-2020",
year = "2020",
month = jul,
day = "1",
doi = "10.1007/978-3-030-53552-0_6",
language = "English",
isbn = "9783030535513",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Gabler",
pages = "40--45",
editor = "Kotsireas, {Ilias S.} and Pardalos, {Panos M.}",
booktitle = "Learning and Intelligent Optimization - 14th International Conference, LION 14, 2020, Revised Selected Papers",
address = "Germany",

}

RIS

TY - GEN

T1 - On finding minimum cardinality subset of vectors with a constraint on the sum of squared euclidean pairwise distances

AU - Eremeev, Anton V.

AU - Kovalyov, Mikhail Y.

AU - Pyatkin, Artem V.

N1 - Publisher Copyright: © Springer Nature Switzerland AG 2020.

PY - 2020/7/1

Y1 - 2020/7/1

N2 - In this paper, we consider the problem of finding a minimum cardinality subset of vectors, given a constraint on the sum of squared Euclidean distances between all vectors of the chosen subset. This problem is closely related to the well-known Maximum Diversity Problem. The main difference consists in swapping the constraint with the optimization criterion. We prove that the problem is NP-hard in the strong sense. 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.

AB - In this paper, we consider the problem of finding a minimum cardinality subset of vectors, given a constraint on the sum of squared Euclidean distances between all vectors of the chosen subset. This problem is closely related to the well-known Maximum Diversity Problem. The main difference consists in swapping the constraint with the optimization criterion. We prove that the problem is NP-hard in the strong sense. 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.

KW - Euclidean space

KW - Exact algorithm

KW - Integer instance

KW - NP-hardness

KW - Pseudo-polynomial time

KW - Subset of points

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

U2 - 10.1007/978-3-030-53552-0_6

DO - 10.1007/978-3-030-53552-0_6

M3 - Conference contribution

AN - SCOPUS:85089211896

SN - 9783030535513

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

SP - 40

EP - 45

BT - Learning and Intelligent Optimization - 14th International Conference, LION 14, 2020, Revised Selected Papers

A2 - Kotsireas, Ilias S.

A2 - Pardalos, Panos M.

PB - Springer Gabler

T2 - 14th International Conference on Learning and Intelligent Optimization, LION 2020

Y2 - 24 May 2020 through 28 May 2020

ER -

ID: 24962158