Clustering to minimize the maximum intercluster distance (Q1059958): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(85)90224-5 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1973264045 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An Analysis of Some Graph Theoretical Cluster Techniques / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Automatische Klassifikation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A graph theoretic approach to the grouping of ordering data / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4181272 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4403756 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Admissible clustering procedures / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Grouping for Maximum Homogeneity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3944005 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Complexity of Near-Optimal Graph Coloring / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3885184 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4749027 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4142699 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Computer-oriented approaches to pattern recognition / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: P-Complete Approximation Problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4138196 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4176809 / rank | |||
Normal rank |
Latest revision as of 18:04, 14 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Clustering to minimize the maximum intercluster distance |
scientific article |
Statements
Clustering to minimize the maximum intercluster distance (English)
0 references
1985
0 references
The problem of clustering a set of points so as to minimize the maximum intercluster distance is studied. An O(kn) approximation algorithm, where n is the number of points and k is the number of clusters, that guarantees solutions with an objective function value within two times the optimal solution value is presented. This approximation algorithm succeeds as long as the set of points satisfies the triangular inequality. We also show that our approximation algorithm is best possible, with respect to the approximation bound, if \(P\neq NP\).
0 references
NP-completeness
0 references
minimizing maximum intercluster distance
0 references
clustering
0 references
approximation algorithm
0 references
triangular inequality
0 references