Maximum diversity problem with squared euclidean distance

Anton V. Eremeev, Alexander V. Kel’manov, Mikhail Y. Kovalyov, Artem V. Pyatkin

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

Аннотация

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.

Язык оригиналаанглийский
Название основной публикацииMathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings
РедакторыMichael Khachay, Panos Pardalos, Yury Kochetov
ИздательSpringer-Verlag GmbH and Co. KG
Страницы541-551
Число страниц11
ISBN (печатное издание)9783030226282
DOI
СостояниеОпубликовано - 1 янв 2019
Событие18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019 - Ekaterinburg, Российская Федерация
Продолжительность: 8 июл 201912 июл 2019

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том11548 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019
СтранаРоссийская Федерация
ГородEkaterinburg
Период08.07.201912.07.2019

    Fingerprint

Цитировать

Eremeev, A. V., Kel’manov, A. V., Kovalyov, M. Y., & Pyatkin, A. V. (2019). Maximum diversity problem with squared euclidean distance. В M. Khachay, P. Pardalos, & Y. Kochetov (Ред.), Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings (стр. 541-551). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 11548 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-030-22629-9_38