Standard
Maximum diversity problem with squared euclidean distance. / Eremeev, Anton V.; Kel’manov, Alexander V.; Kovalyov, Mikhail Y. et al.
Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings. ed. / Michael Khachay; Panos Pardalos; Yury Kochetov. Springer-Verlag GmbH and Co. KG, 2019. p. 541-551 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11548 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Eremeev, AV, Kel’manov, AV, Kovalyov, MY
& Pyatkin, AV 2019,
Maximum diversity problem with squared euclidean distance. in M Khachay, P Pardalos & Y Kochetov (eds),
Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11548 LNCS, Springer-Verlag GmbH and Co. KG, pp. 541-551, 18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019, Ekaterinburg, Russian Federation,
08.07.2019.
https://doi.org/10.1007/978-3-030-22629-9_38APA
Eremeev, A. V., Kel’manov, A. V., Kovalyov, M. Y.
, & Pyatkin, A. V. (2019).
Maximum diversity problem with squared euclidean distance. In M. Khachay, P. Pardalos, & Y. Kochetov (Eds.),
Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings (pp. 541-551). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11548 LNCS). Springer-Verlag GmbH and Co. KG.
https://doi.org/10.1007/978-3-030-22629-9_38Vancouver
Eremeev AV, Kel’manov AV, Kovalyov MY
, Pyatkin AV.
Maximum diversity problem with squared euclidean distance. In Khachay M, Pardalos P, Kochetov Y, editors, Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings. Springer-Verlag GmbH and Co. KG. 2019. p. 541-551. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-22629-9_38
Author
Eremeev, Anton V. ; Kel’manov, Alexander V. ; Kovalyov, Mikhail Y. et al. /
Maximum diversity problem with squared euclidean distance. Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings. editor / Michael Khachay ; Panos Pardalos ; Yury Kochetov. Springer-Verlag GmbH and Co. KG, 2019. pp. 541-551 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{3dfc58d092a94a4caf5b846ba7411f3c,
title = "Maximum diversity problem with squared euclidean distance",
abstract = "In this paper we consider the following Maximum Diversity Subset problem. Given a set of points in Euclidean space, find a subset of size M maximizing the squared Euclidean distances between the chosen points. We propose an exact dynamic programming algorithm for the case of integer input data. If the dimension of the Euclidean space is bounded by a constant, the algorithm has a pseudo-polynomial time complexity. Using this algorithm, we develop an FPTAS for the special case where the dimension of the Euclidean space is bounded by a constant. We also propose a new proof of strong NP-hardness of the problem in the general case.",
keywords = "Euclidean space, Exact algorithm, Fixed space dimension, Given size, Integer instance, Maximum variance, Pseudo-polynomial time, Strong NP-hardness, Subset of points, ALGORITHMS, SUBSET",
author = "Eremeev, {Anton V.} and Kel{\textquoteright}manov, {Alexander V.} and Kovalyov, {Mikhail Y.} and Pyatkin, {Artem V.}",
year = "2019",
month = jan,
day = "1",
doi = "10.1007/978-3-030-22629-9_38",
language = "English",
isbn = "9783030226282",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag GmbH and Co. KG",
pages = "541--551",
editor = "Michael Khachay and Panos Pardalos and Yury Kochetov",
booktitle = "Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings",
address = "Germany",
note = "18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019 ; Conference date: 08-07-2019 Through 12-07-2019",
}
RIS
TY - GEN
T1 - Maximum diversity problem with squared euclidean distance
AU - Eremeev, Anton V.
AU - Kel’manov, Alexander V.
AU - Kovalyov, Mikhail Y.
AU - Pyatkin, Artem V.
PY - 2019/1/1
Y1 - 2019/1/1
N2 - In this paper we consider the following Maximum Diversity Subset problem. Given a set of points in Euclidean space, find a subset of size M maximizing the squared Euclidean distances between the chosen points. We propose an exact dynamic programming algorithm for the case of integer input data. If the dimension of the Euclidean space is bounded by a constant, the algorithm has a pseudo-polynomial time complexity. Using this algorithm, we develop an FPTAS for the special case where the dimension of the Euclidean space is bounded by a constant. We also propose a new proof of strong NP-hardness of the problem in the general case.
AB - In this paper we consider the following Maximum Diversity Subset problem. Given a set of points in Euclidean space, find a subset of size M maximizing the squared Euclidean distances between the chosen points. We propose an exact dynamic programming algorithm for the case of integer input data. If the dimension of the Euclidean space is bounded by a constant, the algorithm has a pseudo-polynomial time complexity. Using this algorithm, we develop an FPTAS for the special case where the dimension of the Euclidean space is bounded by a constant. We also propose a new proof of strong NP-hardness of the problem in the general case.
KW - Euclidean space
KW - Exact algorithm
KW - Fixed space dimension
KW - Given size
KW - Integer instance
KW - Maximum variance
KW - Pseudo-polynomial time
KW - Strong NP-hardness
KW - Subset of points
KW - ALGORITHMS
KW - SUBSET
UR - http://www.scopus.com/inward/record.url?scp=85067677029&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-22629-9_38
DO - 10.1007/978-3-030-22629-9_38
M3 - Conference contribution
AN - SCOPUS:85067677029
SN - 9783030226282
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 541
EP - 551
BT - Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings
A2 - Khachay, Michael
A2 - Pardalos, Panos
A2 - Kochetov, Yury
PB - Springer-Verlag GmbH and Co. KG
T2 - 18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019
Y2 - 8 July 2019 through 12 July 2019
ER -
