A randomized algorithm for 2-partition of a sequence

Alexander Kel’manov, Sergey Khamidullin, Vladimir Khandeev

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

2 Citations (Scopus)

Abstract

In the paper we consider one strongly NP-hard problem of partitioning a finite Euclidean sequence into two clusters minimizing the sum over both clusters of intracluster sum of squared distances from clusters elements to their centers. The cardinalities of clusters are assumed to be given. The center of the first cluster is unknown and is defined as the mean value of all points in the cluster. The center of the second one is the origin. Additionally, the difference between the indexes of two consequent points from the first cluster is bounded from below and above by some constants. A randomized algorithm for the problem is proposed. For an established parameter value, given a relative error ε> 0 and fixed γ∈ (0, 1), this algorithm allows to find a (1 + ε) -approximate solution of the problem with a probability of at least 1 - γ in polynomial time. The conditions are established under which the algorithm is polynomial and asymptotically exact.

Original languageEnglish
Title of host publicationAnalysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers
EditorsWMP VanDerAalst, DI Ignatov, M Khachay, SO Kuznetsov, Lempitsky, IA Lomazova, N Loukachevitch, A Napoli, A Panchenko, PM Pardalos, AV Savchenko, S Wasserman
PublisherSpringer-Verlag GmbH and Co. KG
Pages313-322
Number of pages10
ISBN (Print)9783319730127
DOIs
Publication statusPublished - 1 Jan 2018
Event6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017 - Moscow, Russian Federation
Duration: 27 Jul 201729 Jul 2017

Publication series

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

Conference

Conference6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017
CountryRussian Federation
CityMoscow
Period27.07.201729.07.2017

Keywords

  • Asymptotic accuracy
  • Euclidean space
  • Minimum sum-of-squared distances
  • NP-hardness
  • Partitioning
  • Randomized algorithm
  • Sequence
  • TIME-SERIES DATA
  • NP-hardness Randomized algorithm
  • VECTORS

Fingerprint Dive into the research topics of 'A randomized algorithm for 2-partition of a sequence'. Together they form a unique fingerprint.

Cite this