Randomized algorithms for some clustering problems

Alexander Kel’manov, Vladimir Khandeev, Anna Panasenko

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

8 Citations (Scopus)

Abstract

We consider two strongly NP-hard problems of clustering a finite set of points in Euclidean Space. Both problems have applications, in particular, in data analysis, data mining, pattern recognition, and machine learning. In the first problem, an input set is given and we need to find a cluster (i.e., a subset) of a given size which minimizes the sum of squared distances between the elements of this cluster and its centroid (the geometric center). Every point outside this cluster is considered as singleton cluster. In the second problem, we need to partition a finite set into two clusters minimizing the sum over both clusters of the weighted intracluster sums of the squared distances between the elements of the clusters and their centers. The center of the first cluster is unknown and determined as the centroid, while the center of the second one is the origin. The weight factors for both intracluster sums are the given clusters sizes. In this paper, we present parameterized randomized algorithms for these problems. For given upper bounds of the relative error and failure probability, the parameter value is defined for which both our algorithms find approximate solutions in a polynomial time. This running time is linear on the space dimension and on the input set size. The conditions are found under which these algorithms are asymptotically exact and have the time complexity that is linear on the space dimension and quadratic on the size of the input set.

Original languageEnglish
Title of host publicationOptimization Problems and Their Applications - 7th International Conference, OPTA 2018, Revised Selected Papers
PublisherSpringer-Verlag GmbH and Co. KG
Pages109-119
Number of pages11
ISBN (Print)9783319937991
DOIs
Publication statusPublished - 1 Jan 2018
Event7th International Conference on Optimization Problems and Their Applications, OPTA 2018 - Omsk, Russian Federation
Duration: 8 Jun 201814 Jun 2018

Publication series

NameCommunications in Computer and Information Science
Volume871
ISSN (Print)1865-0929

Conference

Conference7th International Conference on Optimization Problems and Their Applications, OPTA 2018
CountryRussian Federation
CityOmsk
Period08.06.201814.06.2018

Keywords

  • Approximation algorithm
  • Asymptotic accuracy
  • Clustering
  • Euclidean space
  • NP-hardness
  • Randomized

Fingerprint

Dive into the research topics of 'Randomized algorithms for some clustering problems'. Together they form a unique fingerprint.

Cite this