zbMATH — the first resource for mathematics

Clustering to minimize the maximum intercluster distance. (English) Zbl 0567.62048
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\).

62H30 Classification and discrimination; cluster analysis (statistical aspects)
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] Augustson, J.G.; Minker, J., An analysis of some graph theoretical cluster techniques, J. ACM, 17, 571-588, (1970) · Zbl 0206.17701
[2] Bock, H.H., Automatische klassifikation, (1974), Vandenhoek und Ruprecht Gottingen · Zbl 0207.19202
[3] Bodin, L.D., A graph theoretic approach to the grouping of ordering data, Networks, 2, 307-310, (1972) · Zbl 0252.68011
[4] Brucker, P., On the complexity of clustering problems, () · Zbl 0397.68044
[5] Duda, R.; Hart, P., Pattern classification and scene analysis, (1973), Wiley New York · Zbl 0277.68056
[6] Fisher, L.; Van Ness, J., Admissible clustering procedures, Biometrica, 58, 91-104, (1971) · Zbl 0224.62030
[7] Fisher, W.D., On grouping for maximum homogeneity, Jasa, 53, 789-798, (1958) · Zbl 0084.35904
[8] Gonzalez, T.F., On the computational complexity of clustering and related problems, (), 174-182
[9] Garey, M.R.; Johnson, D.S., The complexity of near-optimal graph coloring, J. ACM, 23, 1, 43-69, (1976) · Zbl 0322.05111
[10] Garey, M.R.; Johnson, D.S., ()
[11] Horowitz, E.; Sahni, S., Fundamentals of computer algorithms, (1978), Computer Science Press Potomac · Zbl 0442.68022
[12] Hochbaum, D.S.; Shmoys, D.B., Powers of graphs: A powerful approximation technique for bottleneck problems, ()
[13] Johnson, D.B.; Lafuente, J.M., Controlled single pass classification algorithm with applications to multilevel clustering, ()
[14] Rohlf, F.J., Single link clustering algorithms, () · Zbl 0511.62074
[15] Karp, R.M., Reducibility among combinatorial problems, (), 85-104 · Zbl 0366.68041
[16] Meisel, W.S., Computer-oriented approaches to pattern recognition, (1972), Academic Press New York · Zbl 0252.68063
[17] Sahni, S.; Gonzalez, T.F., P-complete approximation problems, J. ACM, 23, 555-565, (1976) · Zbl 0348.90152
[18] Salton, G., The smart retrieval system, experiments in automatic document processing, (1971), Prentice-Hall Englewood Cliffs, NJ
[19] Salton, G., Dynamic information and library processing, (1975), Prentice-Hall Englewood Cliffs, NJ · Zbl 0363.68134
[20] Shamos, M.I., Geometry and statistics: problems at the interface, (), 251-280
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.