{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T19:57:48Z","timestamp":1760299068090},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662460771"},{"type":"electronic","value":"9783662460788"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-46078-8_11","type":"book-chapter","created":{"date-parts":[[2015,1,14]],"date-time":"2015-01-14T14:54:29Z","timestamp":1421247269000},"page":"128-139","source":"Crossref","is-referenced-by-count":1,"title":["Exact Algorithms for 2-Clustering with Size Constraints in the Euclidean Plane"],"prefix":"10.1007","author":[{"given":"Alberto","family":"Bertoni","sequence":"first","affiliation":[]},{"given":"Massimiliano","family":"Goldwurm","sequence":"additional","affiliation":[]},{"given":"Jianyi","family":"Lin","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s10994-009-5103-0","volume":"75","author":"D. Aloise","year":"2009","unstructured":"Aloise, D., Deshpande, A., Hansen, P., Popat, P.: NP-hardness of Euclidean sum-of-squares clustering. Machine Learning\u00a075, 245\u2013249 (2009)","journal-title":"Machine Learning"},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"Basu, S., Davidson, I., Wagstaff, K.: Constrained Clustering: Advances in Algorithms, Theory, and Applications. Chapman and Hall\/CRC (2008)","DOI":"10.1201\/9781584889977"},{"key":"11_CR3","unstructured":"Bertoni, A., Goldwurm, M., Lin, J., Pini, L.: Size-constrained 2-Clustering in the Plane with Manhattan Distance. In: Proc. 15th Italian Conference on Theoretical Computer Science. CEUR Workshop Proceedings, vol.\u00a01231, pp. 33\u201344. CEUR-WS.org (2014) ISSN 1613-0073"},{"issue":"1","key":"11_CR4","doi-asserted-by":"crossref","first-page":"125","DOI":"10.3233\/FI-2012-644","volume":"115","author":"A. Bertoni","year":"2012","unstructured":"Bertoni, A., Goldwurm, M., Lin, J., Sacc\u00e0, F.: Size Constrained Distance Clustering: Separation Properties and Some Complexity Results. Fundamenta Informaticae\u00a0115(1), 125\u2013139 (2012)","journal-title":"Fundamenta Informaticae"},{"key":"11_CR5","unstructured":"Bishop, C.: Pattern Recognition and Machine Learning. Springer (2006)"},{"key":"11_CR6","unstructured":"Dasgupta, S.: The hardness of k-means clustering. Technical Report CS2007-0890, Department of Computer Science and Engineering, University of California, San Diego (2007)"},{"issue":"3","key":"11_CR7","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/PL00009354","volume":"19","author":"T. Dey","year":"1998","unstructured":"Dey, T.: Improved Bounds for Planar k-Sets and Related Problems. Discrete & Computational Geometry\u00a019(3), 373\u2013382 (1998)","journal-title":"Discrete & Computational Geometry"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Edelsbrunner, H.: Algorithms in Combinatorial Geometry. EATCS monographs on theoretical computer science. Springer (1987)","DOI":"10.1007\/978-3-642-61568-9"},{"key":"11_CR9","first-page":"139","volume-title":"A Survey of Combinatorial Theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971)","author":"P. Erd\u0151s","year":"1973","unstructured":"Erd\u0151s, P., Lov\u00e1sz, L., Simmons, A., Straus, E.G.: Dissection graphs of planar point sets. In: A Survey of Combinatorial Theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971), pp. 139\u2013149. North-Holland, Amsterdam (1973)"},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd edn. Springer (2009)","DOI":"10.1007\/978-0-387-84858-7"},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"Inaba, M., Katoh, N., Imai, H.: Applications of weighted voronoi diagrams and randomization to variance-based k-clustering (extended abstract). In: Proceedings of the Tenth Annual Symposium on Computational Geometry, SCG 1994, USA, pp. 332\u2013339 (1994)","DOI":"10.1145\/177424.178042"},{"key":"11_CR12","unstructured":"Lin. J.: Exact algorithms for size constrained clustering. PhD Thesis, Dottorato di ricerca in Matematica, Statistica e Scienze computationali, Universit\u00e0 degli Studi di Milano. Ledizioni Publishing (2013)"},{"key":"11_CR13","unstructured":"MacQueen, J.B.: Some method for the classification and analysis of multivariate observations. In: Proceedings of the 5th Berkeley Symposium on Mathematical Structures, pp. 281\u2013297 (1967)"},{"key":"11_CR14","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.tcs.2010.05.034","volume":"442","author":"M. Mahajan","year":"2012","unstructured":"Mahajan, M., Nimbhorkar, P., Varadarajan, K.: The planar k-means problem is NP-hard. Theoretical Computer Science\u00a0442, 13\u201321 (2012)","journal-title":"Theoretical Computer Science"},{"key":"11_CR15","doi-asserted-by":"publisher","first-page":"1831","DOI":"10.1016\/j.dam.2009.01.003","volume":"157","author":"B. Novick","year":"2009","unstructured":"Novick, B.: Norm statistics and the complexity of clustering problems. Discrete Applied Mathematics\u00a0157, 1831\u20131839 (2009)","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"11_CR16","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","volume":"23","author":"M.H. Overmars","year":"1981","unstructured":"Overmars, M.H., van Leeuwen, J.: Maintenance of configurations in the plane. J. Comput. Syst. Sci.\u00a023(2), 166\u2013204 (1981)","journal-title":"J. Comput. Syst. Sci."},{"key":"11_CR17","doi-asserted-by":"crossref","unstructured":"Preparata, F., Shamos, M.: Computational geometry: an introduction. Texts and monographs in computer science. Springer (1985)","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"11_CR18","unstructured":"Theodoridis, S., Koutroumbas, K.: Pattern Recognition. Academic Press, Elsevier (2009)"},{"key":"11_CR19","doi-asserted-by":"crossref","unstructured":"Vattani, A.: K-means requires exponentially many iterations even in the plane. In: Proceedings of the 25th Symposium on Computational Geometry (SoCG) (2009)","DOI":"10.1145\/1542362.1542419"},{"key":"11_CR20","unstructured":"Wagstaff, K., Cardie, C.: Clustering with instance-level constraints. In: Proc. of the 17th Intl. Conf. on Machine Learning, pp. 1103\u20131110 (2000)"},{"issue":"8","key":"11_CR21","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1016\/j.knosys.2010.06.003","volume":"23","author":"S. Zhu","year":"2010","unstructured":"Zhu, S., Wang, D., Li, T.: Data clustering with size constraints. Knowledge-Based Systems\u00a023(8), 883\u2013889 (2010)","journal-title":"Knowledge-Based Systems"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2015: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-46078-8_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,29]],"date-time":"2020-08-29T00:34:29Z","timestamp":1598661269000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-46078-8_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662460771","9783662460788"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-46078-8_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}