2-Approximation Polynomial-Time Algorithm for a Cardinality-Weighted 2-Partitioning Problem of a Sequence

Alexander Kel’manov, Sergey Khamidullin, Anna Panasenko

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

1 Citation (Scopus)

Abstract

We consider a problem of 2-partitioning a finite sequence of points in Euclidean space into clusters of the given sizes with some constraints. The solution criterion is the minimum of the sum of weighted intracluster sums of squared distances between the elements of each cluster and its center. The weight of the intracluster sum is equal to the cluster size. The center of one cluster is given as input (is the origin without loss of generality), while the center of the other one is unknown and is determined as a geometric center. The following constraints hold: the difference between the indices of two subsequent points included in the first cluster is bounded from above and below by some given constants. In this paper, we have shown that the considered problem is the strongly NP-hard one and propose a polynomial-time 2-approximation algorithm for solving the problem.

Original languageEnglish
Title of host publicationNumerical Computations
Subtitle of host publicationTheory and Algorithms - 3rd International Conference, NUMTA 2019, Revised Selected Papers
EditorsYaroslav D. Sergeyev, Dmitri E. Kvasov
PublisherSpringer Gabler
Pages386-393
Number of pages8
ISBN (Print)9783030406158
DOIs
Publication statusPublished - 1 Jan 2020
Event3rd Triennial International Conference and Summer School on Numerical Computations: Theory and Algorithms, NUMTA 2019 - Crotone, Italy
Duration: 15 Jun 201921 Jun 2019

Publication series

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

Conference

Conference3rd Triennial International Conference and Summer School on Numerical Computations: Theory and Algorithms, NUMTA 2019
CountryItaly
CityCrotone
Period15.06.201921.06.2019

Keywords

  • Approximation algorithm
  • Euclidean space
  • NP-hard problem
  • Polynomial time
  • Quadratic variation
  • Sequence of points
  • Weighted 2-partition

Fingerprint Dive into the research topics of '2-Approximation Polynomial-Time Algorithm for a Cardinality-Weighted 2-Partitioning Problem of a Sequence'. Together they form a unique fingerprint.

Cite this