PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Size Constrained Distance Clustering: Separation Properties and Some Complexity Results

Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
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
Wydawca
Rocznik
Strony
125--139
Opis fizyczny
Bibliogr. 19 poz.
Twórcy
autor
autor
autor
autor
  • Department of Computer Science, University of Milan, Via Comelico 39/41, 20135 Milan, Italy, jianyi.lin@unimi.it
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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS8-0023-0041
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.