SCIENCE@home

Computational Feasibility of Clustering under Clusterability Assumptions

Shai Ben-David

Published 2015 in arXiv.org

ABSTRACT

It is well known that most of the common clustering objectives are NP-hard to optimize. In practice, however, clustering is being routinely carried out. One approach for providing theoretical understanding of this seeming discrepancy is to come up with notions of clusterability that distinguish realistically interesting input data from worst-case data sets. The hope is that there will be clustering algorithms that are provably efficient on such 'clusterable' instances. In other words, hope that "Clustering is difficult only when it does not matter" (CDNM thesis, for short). We believe that to some extent this may indeed be the case. This paper provides a survey of recent papers along this line of research and a critical evaluation their results. Our bottom line conclusion is that that CDNM thesis is still far from being formally substantiated. We start by discussing which requirements should be met in order to provide formal support the validity of the CDNM thesis. In particular, we list some implied requirements for notions of clusterability. We then examine existing results in view of those requirements and outline some research challenges and open questions.

PUBLICATION RECORD

  • Publication year

    2015

  • Venue

    arXiv.org

  • Publication date

    2015-01-02

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    arXiv 1501.00437
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-22 of 22 references · Page 1 of 1

CITED BY

Showing 1-37 of 37 citing papers · Page 1 of 1