Exact algorithms for two quadratic euclidean problems of searching for the largest subset and longest subsequence

Alexander Kel’manov, Sergey Khamidullin, Vladimir Khandeev, Artem Pyatkin

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

2 Цитирования (Scopus)

Аннотация

The following two strongly NP-hard problems are considered. In the first problem, we need to find in the given finite set of points in Euclidean space the subset of largest size such that the sum of squared distances between the elements of this subset and its unknown centroid (geometrical center) does not exceed a given percentage of the sum of squared distances between the elements of the input set and its centroid. In the second problem, the input is a sequence (not a set) and we have some additional constraints on the indices of the elements of the chosen subsequence under the same restriction on the sum of squared distances as in the first problem. Both problems can be treated as data editing problems aimed to find similar elements and removal of extraneous (dissimilar) elements. We propose exact algorithms for the cases of both problems in which the input points have integer-valued coordinates. If the space dimension is bounded by some constant, our algorithms run in a pseudopolynomial time. Some results of numerical experiments illustrating the performance of the algorithms are presented.

Язык оригиналаанглийский
Название основной публикацииLearning and Intelligent Optimization - 12th International Conference, LION 12, Revised Selected Papers
ИздательSpringer-Verlag GmbH and Co. KG
Страницы326-336
Число страниц11
ISBN (печатное издание)9783030053475
DOI
СостояниеОпубликовано - 1 янв 2019
Событие12th International Conference on Learning and Intelligent Optimization, LION 12 - Kalamata, Греция
Продолжительность: 10 июн 201815 июн 2018

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

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

Конференция

Конференция12th International Conference on Learning and Intelligent Optimization, LION 12
СтранаГреция
ГородKalamata
Период10.06.201815.06.2018

Fingerprint Подробные сведения о темах исследования «Exact algorithms for two quadratic euclidean problems of searching for the largest subset and longest subsequence». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Kel’manov, A., Khamidullin, S., Khandeev, V., & Pyatkin, A. (2019). Exact algorithms for two quadratic euclidean problems of searching for the largest subset and longest subsequence. В Learning and Intelligent Optimization - 12th International Conference, LION 12, Revised Selected Papers (стр. 326-336). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 11353 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-030-05348-2_28