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

Anton V. Eremeev, Mikhail Y. Kovalyov, Artem V. Pyatkin

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

Аннотация

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.

Язык оригиналаанглийский
Название основной публикацииLearning and Intelligent Optimization - 14th International Conference, LION 14, 2020, Revised Selected Papers
РедакторыIlias S. Kotsireas, Panos M. Pardalos
ИздательSpringer Gabler
Страницы40-45
Число страниц6
ISBN (печатное издание)9783030535513
DOI
СостояниеОпубликовано - 1 июл 2020
Событие14th International Conference on Learning and Intelligent Optimization, LION 2020 - Athens, Греция
Продолжительность: 24 мая 202028 мая 2020

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

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

Конференция

Конференция14th International Conference on Learning and Intelligent Optimization, LION 2020
СтранаГреция
ГородAthens
Период24.05.202028.05.2020

Fingerprint Подробные сведения о темах исследования «On finding minimum cardinality subset of vectors with a constraint on the sum of squared euclidean pairwise distances». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    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. В I. S. Kotsireas, & P. M. Pardalos (Ред.), Learning and Intelligent Optimization - 14th International Conference, LION 14, 2020, Revised Selected Papers (стр. 40-45). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 12096 LNCS). Springer Gabler. https://doi.org/10.1007/978-3-030-53552-0_6