Clustering with lower-bounded sizes

LAUR Repository

Show simple item record

dc.contributor.author Abu-Khzam, Faisal N.
dc.contributor.author Bazgan, Cristina
dc.contributor.author Casel, Katrin
dc.contributor.author Fernau, Henning
dc.date.accessioned 2018-04-24T06:06:34Z
dc.date.available 2018-04-24T06:06:34Z
dc.date.copyright 2017 en_US
dc.date.issued 2018-04-24
dc.identifier.issn 1432-0541 en_US
dc.identifier.uri http://hdl.handle.net/10725/7493
dc.description.abstract Classical clustering problems search for a partition of objects into a fixed number of clusters. In many scenarios, however, the number of clusters is not known or necessarily fixed. Further, clusters are sometimes only considered to be of significance if they have a certain size. We discuss clustering into sets of minimum cardinality k without a fixed number of sets and present a general model for these types of problems. This general framework allows the comparison of different measures to assess the quality of a clustering. We specifically consider nine quality-measures and classify the complexity of the resulting problems with respect to k. Further, we derive some polynomial-time solvable cases for k=2 with connections to matching-type problems which, among other graph problems, then are used to compute approximations for larger values of k. en_US
dc.language.iso en en_US
dc.title Clustering with lower-bounded sizes en_US
dc.type Article en_US
dc.description.version Published en_US
dc.author.school SAS en_US
dc.author.idnumber 200302941 en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.relation.journal Algorithmica en_US
dc.article.pages 1-34 en_US
dc.keywords Clustering en_US
dc.keywords Computational complexity en_US
dc.keywords Approximation algorithms en_US
dc.keywords Anonymisation en_US
dc.identifier.doi http://dx.doi.org/10.1007/s00453-017-0374-5 en_US
dc.identifier.ctation Abu-Khzam, F. N., Bazgan, C., Casel, K., & Fernau, H. Clustering with Lower-Bounded Sizes. Algorithmica, 1-34. en_US
dc.author.email faisal.abukhzam@lau.edu.lb en_US
dc.identifier.tou http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php en_US
dc.identifier.url https://link.springer.com/article/10.1007%2Fs00453-017-0374-5 en_US
dc.orcid.id https://orcid.org/0000-0001-5221-8421 en_US
dc.author.affiliation Lebanese American University en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account