A PTAS for one cardinality-weighted 2-clustering problem

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

2 Citations (Scopus)

Abstract

We consider one strongly NP-hard problem of clustering a finite set of points in Euclidean space. In this problem, we need to partition a finite set of points into two clusters minimizing the sum over both clusters of the weighted intracluster sums. Each of these sums is the sum of squared distances between the elements of the cluster and their center. The center of the one cluster is unknown and determined as the centroid, while the center of the other one is fixed at the origin. The weight factors for both intracluster sums are the given sizes of the clusters. In this paper, we present an approximation algorithm for the problem and prove that it is a polynomial-time approximation scheme (PTAS).

Original languageEnglish
Title of host publicationMathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings
EditorsMichael Khachay, Panos Pardalos, Yury Kochetov
PublisherSpringer-Verlag GmbH and Co. KG
Pages581-592
Number of pages12
ISBN (Print)9783030226282
DOIs
Publication statusPublished - 1 Jan 2019
Event18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019 - Ekaterinburg, Russian Federation
Duration: 8 Jul 201912 Jul 2019

Publication series

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

Conference

Conference18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019
CountryRussian Federation
CityEkaterinburg
Period08.07.201912.07.2019

Keywords

  • Approximation algorithm
  • Euclidean space
  • NP-hardness
  • PTAS
  • Quadratic variation
  • Weighted 2-clustering
  • APPROXIMATION SCHEME
  • ALGORITHM

Fingerprint

Dive into the research topics of 'A PTAS for one cardinality-weighted 2-clustering problem'. Together they form a unique fingerprint.

Cite this