Exact algorithms for 2-clustering with size constraints in the Euclidean plane. Bertoni, A., Goldwurm, M., & Lin, J. Volume 8939 , 2015. abstract bibtex © Springer-Verlag Berlin Heidelberg 2015. We study the problem of determining an optimal bipartition A,B of a set X of n points in R2 that minimizes the sum of the sample variances of A and B, under the size constraints |A| = k and |B| = n–k. We present two algorithms for such a problem. The first one computes the solution in O(n3√k log2 n) time by using known results on convexhulls and k-sets. The second algorithm, for an input X ⊂ R2 of size n, solves the problem for all k = 1, 2,..., ⌊n/2⌋ and works in O(n2 log n) time.
@book{
title = {Exact algorithms for 2-clustering with size constraints in the Euclidean plane},
type = {book},
year = {2015},
source = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
keywords = {Algorithms for clustering,Cluster size constraints,Data analysis,Euclidean distance,Machine learning},
volume = {8939},
id = {1a48dce1-79fd-36ea-99f2-cf33160c289a},
created = {2018-08-01T13:07:25.316Z},
file_attached = {false},
profile_id = {6bce6ab9-03b5-36ad-a474-26e482dc52c3},
last_modified = {2018-08-01T13:07:25.316Z},
read = {false},
starred = {false},
authored = {true},
confirmed = {false},
hidden = {false},
private_publication = {true},
abstract = {© Springer-Verlag Berlin Heidelberg 2015. We study the problem of determining an optimal bipartition A,B of a set X of n points in R<sup>2</sup> that minimizes the sum of the sample variances of A and B, under the size constraints |A| = k and |B| = n–k. We present two algorithms for such a problem. The first one computes the solution in O(n<sup>3</sup>√k log<sup>2</sup> n) time by using known results on convexhulls and k-sets. The second algorithm, for an input X ⊂ R<sup>2</sup> of size n, solves the problem for all k = 1, 2,..., ⌊n/2⌋ and works in O(n<sup>2</sup> log n) time.},
bibtype = {book},
author = {Bertoni, A. and Goldwurm, M. and Lin, J.}
}
Downloads: 0
{"_id":"49HMCfbdAFT7vj8fD","bibbaseid":"bertoni-goldwurm-lin-exactalgorithmsfor2clusteringwithsizeconstraintsintheeuclideanplane-2015","downloads":0,"creationDate":"2016-03-02T16:03:18.127Z","title":"Exact algorithms for 2-clustering with size constraints in the Euclidean plane","author_short":["Bertoni, A.","Goldwurm, M.","Lin, J."],"year":2015,"bibtype":"book","biburl":"https://bibbase.org/service/mendeley/6bce6ab9-03b5-36ad-a474-26e482dc52c3","bibdata":{"title":"Exact algorithms for 2-clustering with size constraints in the Euclidean plane","type":"book","year":"2015","source":"Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)","keywords":"Algorithms for clustering,Cluster size constraints,Data analysis,Euclidean distance,Machine learning","volume":"8939","id":"1a48dce1-79fd-36ea-99f2-cf33160c289a","created":"2018-08-01T13:07:25.316Z","file_attached":false,"profile_id":"6bce6ab9-03b5-36ad-a474-26e482dc52c3","last_modified":"2018-08-01T13:07:25.316Z","read":false,"starred":false,"authored":"true","confirmed":false,"hidden":false,"private_publication":"true","abstract":"© Springer-Verlag Berlin Heidelberg 2015. We study the problem of determining an optimal bipartition A,B of a set X of n points in R<sup>2</sup> that minimizes the sum of the sample variances of A and B, under the size constraints |A| = k and |B| = n–k. We present two algorithms for such a problem. The first one computes the solution in O(n<sup>3</sup>√k log<sup>2</sup> n) time by using known results on convexhulls and k-sets. The second algorithm, for an input X ⊂ R<sup>2</sup> of size n, solves the problem for all k = 1, 2,..., ⌊n/2⌋ and works in O(n<sup>2</sup> log n) time.","bibtype":"book","author":"Bertoni, A. and Goldwurm, M. and Lin, J.","bibtex":"@book{\n title = {Exact algorithms for 2-clustering with size constraints in the Euclidean plane},\n type = {book},\n year = {2015},\n source = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},\n keywords = {Algorithms for clustering,Cluster size constraints,Data analysis,Euclidean distance,Machine learning},\n volume = {8939},\n id = {1a48dce1-79fd-36ea-99f2-cf33160c289a},\n created = {2018-08-01T13:07:25.316Z},\n file_attached = {false},\n profile_id = {6bce6ab9-03b5-36ad-a474-26e482dc52c3},\n last_modified = {2018-08-01T13:07:25.316Z},\n read = {false},\n starred = {false},\n authored = {true},\n confirmed = {false},\n hidden = {false},\n private_publication = {true},\n abstract = {© Springer-Verlag Berlin Heidelberg 2015. We study the problem of determining an optimal bipartition A,B of a set X of n points in R<sup>2</sup> that minimizes the sum of the sample variances of A and B, under the size constraints |A| = k and |B| = n–k. We present two algorithms for such a problem. The first one computes the solution in O(n<sup>3</sup>√k log<sup>2</sup> n) time by using known results on convexhulls and k-sets. The second algorithm, for an input X ⊂ R<sup>2</sup> of size n, solves the problem for all k = 1, 2,..., ⌊n/2⌋ and works in O(n<sup>2</sup> log n) time.},\n bibtype = {book},\n author = {Bertoni, A. and Goldwurm, M. and Lin, J.}\n}","author_short":["Bertoni, A.","Goldwurm, M.","Lin, J."],"biburl":"https://bibbase.org/service/mendeley/6bce6ab9-03b5-36ad-a474-26e482dc52c3","bibbaseid":"bertoni-goldwurm-lin-exactalgorithmsfor2clusteringwithsizeconstraintsintheeuclideanplane-2015","role":"author","urls":{},"keyword":["Algorithms for clustering","Cluster size constraints","Data analysis","Euclidean distance","Machine learning"],"metadata":{"authorlinks":{}},"downloads":0},"search_terms":["exact","algorithms","clustering","size","constraints","euclidean","plane","bertoni","goldwurm","lin"],"keywords":["algorithms for clustering","cluster size constraints","data analysis","euclidean distance","machine learning"],"authorIDs":[],"dataSources":["KrZZ3KEZ3zvS84wws","Dnwc9S3jN5vmSeyun"]}