Size Constrained Distance Clustering: Separation Properties and Some Complexity Results

• Autorzy: Bertoni A. , Goldwurm M. , Lin J. , Sacca F.
• Języki publikacji: EN

Abstrakty

EN

In this paper we study the complexity of some size constrained clustering problems with norm Lp. We obtain the following results: (i) A separation property for the constrained 2-clustering problem. This implies that the optimal solutions in the 1-dimensional case verify the so-called "String Property"; (ii) The NP-hardness of the constrained 2-clustering problem for every norm Lp (p > 1); (iii) A polynomial time algorithmfor the constrained 2-clustering problemin dimension 1 for every norm Lp with integer p. We also give evidence that this result cannot be extended to norm Lp with rational non-integer p; (iv) The NP-hardness of the constrained clustering problem in dimension 1 for every norm Lp (p ≥1).

Słowa kluczowe

EN

clustering; size constraints; NP-hardness

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 115, nr 1
• Strony: 125--139
• Opis fizyczny: Bibliogr. 19 poz.

Twórcy

autor

Bertoni A.

autor

Goldwurm M.

autor

Lin J.

autor

Sacca F.

• Department of Computer Science, University of Milan, Via Comelico 39/41, 20135 Milan, Italy,

Bibliografia

• [1] Allender, E., Bürgisser, P., Kjeldgaard-Pedersen, J., Miltersen, P. B.: On the Complexity of Numerical Analysis, Proc. 21st Ann. IEEE Conf. on Computational Complexity (CCC'06), 2006.
• [2] Aloise, D., Deshpande, A., Hansen, P., Popat, P.: NP-hardness of Euclidean sum-of-squares clustering, Machine Learning, 75, 2009, 245-249.
• [3] Bradley, P. S., Bennett, K. P., Demiriz, A.: Constrained K-Means Clustering, Technical Report MSR-TR-2000-65,Miscrosoft Research Publication,May 2000.
• [4] Canny, J.: The complexity of robot motion planning, MIT Press, Cambridge,MA, USA, 1988.
• [5] Fisher, W. D.: On Grouping for Maximum Homogeneity, Journal of the American Statistical Association, 53(284), 1958, 789-798.
• [6] Garey, M., Graham, R., Johnson, D.: Some NP-complete geometric problems, Proceedings of the eighth annual ACM symposium on Theory of Computing, ACM New York, NY, USA, 1976.
• [7] Garey, M., Johnson, D., Stockmeyer., L.: Some simplified NP-complete graph problems, Theor. Comput. Sci., 1(3), 1976, 237-267.
• [8] Garey,M. R., Johnson, D. S.: Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, 1979, ISBN 0716710447.
• [9] Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd edition, Springer-Verlag, 2009.
• [10] Hulett, H., Will, T. G.,Woeginger, G. J.: Multigraph realizations of degree sequences: Maximization is easy, minimization is hard, Operations Research Letters, 36(5), 2008, 594 - 596.
• [11] Lloyd, S.: Least squares quantization in PCM, IEEE Transactions on Information Theory, 28(2), 1982, 129-137, ISSN 0018-9448.
• [12] MacQueen, J. B.: Some method for the classification and analysis of multivariate observations, Proceedings of the 5th Berkeley Symposium on Mathematical Structures, 1967.
• [13] Mahajan, M., Nimbhorkar, P., Varadarajan, K.: The Planar k-Means Problem is NP-Hard, in: WALCOM: Algorithms and Computation (S. Das, R. Uehara, Eds.), vol. 5431 of Lecture Notes in Computer Science, Springer Berlin/Heidelberg, 2009, 274-285.
• [14] Novick, B.: Norm statistics and the complexity of clustering problems, Discrete Applied Mathematics, 157, 2009, 1831-1839.
• [15] Tung, A., Han, J., Lakshmanan, L., Ng, R.: Constraint-Based Clustering in Large Databases, in: Database Theory ICDT 2001 (J. Van den Bussche, V. Vianu, Eds.), vol. 1973 of Lecture Notes in Computer Science, Springer Berlin/Heidelberg, 2001, 405-419.
• [16] Vattani, A.: K-means requires exponentially many iterations even in the plane, Proceedings of the 25th Symposium on Computational Geometry (SoCG), 2009.
• [17] Wagner, K. W.: The complexity of combinatorial problems with succinct input representation, Acta Informatica, 23(3), 1986, 325-356.
• [18] Wagstaff, K., Cardie, C.: Clustering with Instance-level Constraints, Proc. of the 17th Intl. Conf. on Machine Learning, 2000.
• [19] Zhu, S., Wang, D., Li., T.: Data clustering with size constraints, Knowledge-Based Systems, 23(8), 2010, 883-889.