@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",
}