Exact algorithms for the special cases of two hard to solve problems of searching for the largest subset

Alexander Kel’manov, Vladimir Khandeev, Anna Panasenko

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

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

Аннотация

We consider two problems of searching for the largest subset in a finite set of points in Euclidean space. Both problems have applications, in particular, in data analysis and data approximation. In each problem, an input set and a positive real number are given and it is required to find a subset (i.e., a cluster) of the largest size under a constraint on the value of a quadratic function. The points in the input set which are outside the sought subset are treated as a second cluster. In the first problem, the function in the constraint is the sum over both clusters of the intracluster sums of the squared distances between the elements of the clusters and their centers. The center of the first (i.e., sought) cluster is unknown and determined as the centroid, while the center of the second one is fixed in a given point in Euclidean space (without loss of generality in the origin). In the second problem, the function in the constraint is the sum over both clusters of the weighted intracluster sums of the squared distances between the elements of the clusters and their centers. As in the first problem, the center of the first cluster is unknown and determined as the centroid, while the center of the second one is fixed in the origin. In this paper, we show that both problems are strongly NP-hard. Also, we present exact algorithms for the cases of these problems in which the input points have integer components. If the space dimension is bounded by some constant, the algorithms are pseudopolynomial.

Язык оригиналаанглийский
Название основной публикацииAnalysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers
РедакторыAlexander Panchenko, Wil M. van der Aalst, Michael Khachay, Panos M. Pardalos, Vladimir Batagelj, Natalia Loukachevitch, Goran Glavaš, Dmitry I. Ignatov, Sergei O. Kuznetsov, Olessia Koltsova, Irina A. Lomazova, Andrey V. Savchenko, Amedeo Napoli, Marcello Pelillo
ИздательSpringer-Verlag GmbH and Co. KG
Страницы294-304
Число страниц11
ISBN (печатное издание)9783030110260
DOI
СостояниеОпубликовано - 1 янв 2018
Событие7th International Conference on Analysis of Images, Social Networks and Texts, AIST 2018 - Moscow, Российская Федерация
Продолжительность: 5 июл 20187 июл 2018

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

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

Конференция

Конференция7th International Conference on Analysis of Images, Social Networks and Texts, AIST 2018
СтранаРоссийская Федерация
ГородMoscow
Период05.07.201807.07.2018

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

  • Цитировать

    Kel’manov, A., Khandeev, V., & Panasenko, A. (2018). Exact algorithms for the special cases of two hard to solve problems of searching for the largest subset. В A. Panchenko, W. M. van der Aalst, M. Khachay, P. M. Pardalos, V. Batagelj, N. Loukachevitch, G. Glavaš, D. I. Ignatov, S. O. Kuznetsov, O. Koltsova, I. A. Lomazova, A. V. Savchenko, A. Napoli, & M. Pelillo (Ред.), Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018, Revised Selected Papers (стр. 294-304). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 11179 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-030-11027-7_28