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

Alexander Kel’manov, Vladimir Khandeev

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationAnalysis of Images, Social Networks and Texts - 8th International Conference, AIST 2019, Revised Selected Papers
EditorsWil 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
PublisherSpringer International Publishing AG
Pages377-387
Number of pages11
ISBN (Print)9783030373337
DOIs
Publication statusPublished - 1 Jan 2019
Event8th International Conference on Analysis of Images, Social Networks and Texts, AIST 2019 - Kazan, Russian Federation
Duration: 17 Jul 201919 Jul 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11832 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference8th International Conference on Analysis of Images, Social Networks and Texts, AIST 2019
CountryRussian Federation
CityKazan
Period17.07.201919.07.2019

Keywords

  • 2-clustering
  • 2-partitioning
  • Euclidean space
  • Fast exact algorithms
  • NP-hardness
  • Polynomial-time solvability in the 1D case

Fingerprint

Dive into the research topics of 'Fast and exact algorithms for some NP-hard 2-clustering problems in the one-dimensional case'. Together they form a unique fingerprint.

Cite this