Fast and exact algorithms for some NP-hard 2-clustering problems in the one-dimensional case

Alexander Kel’manov, Vladimir Khandeev

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

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

Аннотация

We consider several well-known optimization 2-clustering (2-partitioning) problems of a finite set of points in Euclidean space. All clustering problems considered are induced by applied problems in Data analysis, Data cleaning, and Data mining. In the general case, all these optimization problems are strongly NP-hard. In the paper, we present a brief overview of the results on the problems computational complexity and on their solvability in the one-dimensional case. We present and propose well-known and new, simple and fast exact algorithms with O(N log N) and O(N) running times for the one-dimensional case of these problems.

Язык оригиналаанглийский
Название основной публикацииAnalysis of Images, Social Networks and Texts - 8th International Conference, AIST 2019, Revised Selected Papers
РедакторыWil M.P. van der Aalst, Vladimir Batagelj, Dmitry I. Ignatov, Valentina Kuskova, Sergei O. Kuznetsov, Irina A. Lomazova, Michael Khachay, Andrey Kutuzov, Natalia Loukachevitch, Amedeo Napoli, Panos M. Pardalos, Marcello Pelillo, Andrey V. Savchenko, Elena Tutubalina
ИздательSpringer International Publishing AG
Страницы377-387
Число страниц11
ISBN (печатное издание)9783030373337
DOI
СостояниеОпубликовано - 1 янв 2019
Событие8th International Conference on Analysis of Images, Social Networks and Texts, AIST 2019 - Kazan, Российская Федерация
Продолжительность: 17 июл 201919 июл 2019

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

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

Конференция

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

Fingerprint Подробные сведения о темах исследования «Fast and exact algorithms for some NP-hard 2-clustering problems in the one-dimensional case». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Kel’manov, A., & Khandeev, V. (2019). Fast and exact algorithms for some NP-hard 2-clustering problems in the one-dimensional case. В W. M. P. van der Aalst, V. Batagelj, D. I. Ignatov, V. Kuskova, S. O. Kuznetsov, I. A. Lomazova, M. Khachay, A. Kutuzov, N. Loukachevitch, A. Napoli, P. M. Pardalos, M. Pelillo, A. V. Savchenko, & E. Tutubalina (Ред.), Analysis of Images, Social Networks and Texts - 8th International Conference, AIST 2019, Revised Selected Papers (стр. 377-387). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 11832 LNCS). Springer International Publishing AG. https://doi.org/10.1007/978-3-030-37334-4_34