Exact Algorithms of Search for a Cluster of the Largest Size in Two Integer 2-Clustering Problems

A. V. Kel′manov, A. V. Panasenko, V. I. Khandeev

Research output: Contribution to journalArticlepeer-review

Abstract

We consider two related discrete optimization problems of searching for a subset in a finite set of points in Euclidean space. Both problems are induced by versions of a fundamental problem in data analysis, namely, that of selecting a subset of similar elements in a set of objects. In each problem, given an input set and a positive real number, it is required to find a cluster (i.e., a subset) of the largest size under constraints on a quadratic clusterization function. The points in the input set, which are outside the sought-for subset, are treated as a second (complementary) cluster. In the first problem, the function under the constraint is the sum over both clusters of the intracluster sums of the squared distances between the elements of the clusters and their centers. The center of the first (i.e., the sought-for) cluster is unknown and determined as a centroid, while the center of the second one is fixed at a given point in Euclidean space (without loss of generality, at the origin of coordinates). In the second problem, the function under the constraint is the sum over both clusters of the weighted intracluster sums of the squared distances between the elements of the clusters and their centers. As in the first problem, the center of the first cluster is unknown and determined as a centroid, while the center of the second one is fixed at the origin of coordinates. In this paper, we show that both problems are strongly NP-hard. Also, we present exact algorithms for the problems in which the input points have integer components. If the space dimension is bounded by some constant, the algorithms are pseudopolynomial.

Original languageEnglish
Pages (from-to)105-115
Number of pages11
JournalNumerical Analysis and Applications
Volume12
Issue number2
DOIs
Publication statusPublished - 1 Apr 2019

Keywords

  • 2-clustering
  • Euclidean space
  • exact algorithm
  • largest subset
  • NP-hardness
  • pseudopolynomial-time solvability

Fingerprint Dive into the research topics of 'Exact Algorithms of Search for a Cluster of the Largest Size in Two Integer 2-Clustering Problems'. Together they form a unique fingerprint.

Cite this