Pseudopolynomial time solvability of a quadratic Euclidean problem of finding a family of disjoint subsets

A. E. Galashov, A. V. Kel’manov

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

In this paper, a strongly NP-hard problem of finding a family of disjoint subsets with given cardinalities in a finite set of points from a Euclidean space is considered. Minimization of the sum over all required subsets of the sum of the squared distances from the elements of these subsets to their geometric centers is used as the search criterion. It is proved that if the coordinates of the input points are integer and the space dimension and the number of required subsets are fixed (i.e., bounded by some constants), the problem is a pseudopolynomial time solvable one.

Original languageEnglish
Pages (from-to)11-16
Number of pages6
JournalNumerical Analysis and Applications
Volume10
Issue number1
DOIs
Publication statusPublished - 1 Jan 2017

Keywords

  • clustering
  • Euclidean space
  • exact pseudopolynomial time algorithm
  • NP-hard problem
  • subsets search

Fingerprint Dive into the research topics of 'Pseudopolynomial time solvability of a quadratic Euclidean problem of finding a family of disjoint subsets'. Together they form a unique fingerprint.

Cite this