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 language | English |
---|---|
Pages (from-to) | 242-248 |
Number of pages | 7 |
Journal | Journal of Applied and Industrial Mathematics |
Volume | 14 |
Issue number | 2 |
DOIs | |
Publication status | Published - 1 May 2020 |
Keywords
- data mining
- NP-hard problem
- p-median problem
- rival similarity
- typical representative