J-MEANS: A new local search heuristic for minimum sum of squares clustering. (English) Zbl 1012.68873


68U99 Computing methodologies and applications
68T10 Pattern recognition, speech recognition


Full Text: DOI


[1] P. Brucker, On the Complexity of Clustering Problems, Lecture Notes in Economics and Mathematical Systems, Springer, Berlin, Vol. 157, 1978, pp. 45-54. · Zbl 0397.68044
[2] Hathaway, R.J, Another interpretation of the EM algorithm for mixture distributions, Statist. probab. lett., 4, 53-56, (1986) · Zbl 0585.62052
[3] Celeux, G; Govaert, G, A classification EM algorithm for clustering and two stochastic versions, Comput. statist. data. anal., 14, 315-332, (1992) · Zbl 0937.62605
[4] O. du Merle, P. Hansen, B. Jaumard, N. Mladenović, An interior point algorithm for minimum sum of squares clustering, Les Cahiers du GERAD G-97-53, Montreal, Canada, 1997, SIAM J. Sci. Comput., to appear.
[5] Koontz, W.L.G; Narendra, P.M; Fukunaga, K, A branch and bound clustering algorithm, IEEE trans. comput., C-24, 908-915, (1975) · Zbl 0308.68039
[6] Diehr, G, Evaluation of a branch and bound algorithm for clustering, SIAM J. sci. statist. comput., 6, 268-284, (1985) · Zbl 0561.65097
[7] Goffin, J.L; Haurie, A; Vial, J.-P, Decomposition and nondifferentiable optimization with the projective algorithm, Mgmt. sci., 38, 284-302, (1992) · Zbl 0762.90050
[8] R.A. Fisher, The use of multiple measurements in taxonomic problems, Ann. Eugenics Part II, VII (1936) 179-188.
[9] Jancey, R.C, Multidimensional group analysis, Austral. J. botany, 14, 127-130, (1966)
[10] J.B. MacQueen, Some methods for classification and analysis of multivariate observations, Proceeding of the 5th Berkeley Symposium on Mathematical Statistics and Probability, Vol. 2, 1967, pp. 281-297. · Zbl 0214.46201
[11] R. Howard, in: J.R. Lawrence (Ed.), Classifying a population into homogeneous groups, Operational Research in the Social Sciences, Tavistock Publ., London, 1966.
[12] Klein, R.W; Dubes, R.C, Experiments in projection and clustering by simulated annealing, Pattern recognition, 22, 213-220, (1989) · Zbl 0709.62613
[13] Al-Sultan, K.H, A tabu search approach to the clustering problem, Pattern recognition, 28, 1443-1451, (1995)
[14] Babu, G.P; Murty, M.N, A near-optimal initial seed value selection in k-means algorithm, using genetic algorithm, Pattern recognition lett., 14, 763-769, (1993) · Zbl 0802.68116
[15] N. Mladenović, A variable neighborhood algorithm — a new metaheuristic for combinatorial optimization, Abstracts of papers presented at Optimization Days, Montréal, 1995, p. 112.
[16] Mladenović, N; Hansen, P, Variable neighborhood search, Comput. oper. res., 24, 1097-1100, (1997) · Zbl 0889.90119
[17] P. Hansen, N. Mladenović, in: S. Voss et al. (Eds.), An introduction to variable neighborhood search, Meta-heuristics advances and trends in local search paradigms for optimization, MIC97, Kluwer, Dordrecht, 1998, pp. 433-458.
[18] H. Späth, Cluster Analysis Algorithms for Data Reduction and Classification of Objects, Ellis Horwood, Chichester, 1980.
[19] Cooper, L, Location – allocation problems, Oper. res., 11, 331-343, (1963) · Zbl 0113.14201
[20] Maranzana, F.E, On the location of supply points to minimize transportation costs, Oper. res. quart., 12, 138-139, (1964)
[21] Brimberg, J; Mladenović, N, Degeneracy in the multi-source Weber problem, Math. programming, 85, 213-220, (1999) · Zbl 0956.90016
[22] Whitaker, R, A fast algorithm for the greedy interchange for large-scale clustering and Median location problems, Inform., 21, 95-108, (1983) · Zbl 0527.90017
[23] Hansen, P; Mladenović, N, Variable neighborhood search for the p-Median, Location sci., 5, 207-226, (1997) · Zbl 0928.90043
[24] J. Brimberg, P. Hansen, N. Mladenović, É. Taillard, Improvements and comparison of heuristics for solving the multisource Weber problem, Les Cahiers du GERAD G-97-37, Montréal, Canada 1997, Oper. Res., to appear.
[25] Reinelt, G, TSP-LIB-A traveling salesman library, ORSA J. comput., 3, 376-384, (1991) · Zbl 0775.90293
[26] E.B. Baum, Toward practical ‘neural’ computation for combinatorial optimization problems, in: J. Denker (Ed.), Neural Networks for Computing, American Institute of Physics, 1986.
[27] Boese, K.D; Kahng, A.B; Muddu, S, A new adaptive multi – start technique for combinatorial global optimizations, Oper. res. lett., 16, 101-113, (1994) · Zbl 0812.90126
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.