Building clusters with lower-bounded sizes

Faisal Abu-Khzam, Cristina Bazgan, Katrin Casel, Henning Fernau

    Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedingspeer-review


    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.

    Original languageEnglish
    Title of host publication27th International Symposium on Algorithms and Computation, ISAAC 2016
    EditorsSeok-Hee Hong
    PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
    Number of pages13
    ISBN (Electronic)9783959770262
    Publication statusPublished - 1 Dec 2016
    EventInternational Symposium on Algorithms and Computation (ISAAC 2016 27th) - Sydney, Australia
    Duration: 12 Dec 201614 Dec 2016
    Conference number: 2016 (27th)


    ConferenceInternational Symposium on Algorithms and Computation (ISAAC 2016 27th)
    Abbreviated titleISAAC


    Dive into the research topics of 'Building clusters with lower-bounded sizes'. Together they form a unique fingerprint.

    Cite this