Computational Complexity of the Problem of Choosing Typical Representatives in a 2-Clustering of a Finite Set of Points in a Metric Space

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the computational complexity of one extremal problem of choosing a subsetof p points from some given 2-clustering of a finite set in a metric space. Thechosen subset of points has to describe the given clusters in the best way from the viewpoint ofsome geometric criterion. This is a formalization of an applied problem of data mining whichconsists in finding a subset of typical representatives of a dataset composed of two classes basedon the function of rival similarity. The problem is proved to be NP-hard. To this end, wepolynomially reduce to the problem one of the well-known problems NP-hard in the strong sense,the p-median problem.

Original languageEnglish
Pages (from-to)242-248
Number of pages7
JournalJournal of Applied and Industrial Mathematics
Volume14
Issue number2
DOIs
Publication statusPublished - 1 May 2020

Keywords

  • data mining
  • NP-hard problem
  • p-median problem
  • rival similarity
  • typical representative

Fingerprint

Dive into the research topics of 'Computational Complexity of the Problem of Choosing Typical Representatives in a 2-Clustering of a Finite Set of Points in a Metric Space'. Together they form a unique fingerprint.

Cite this