• DocumentCode
    3449993
  • Title

    A sublinear time approximation scheme for clustering in metric spaces

  • Author

    Indyk, Piotr

  • Author_Institution
    Stanford Univ., CA, USA
  • fYear
    1999
  • fDate
    1999
  • Firstpage
    154
  • Lastpage
    159
  • Abstract
    The metric 2-clustering problem is defined as follows: given a metric (or weighted graph) (X,d), partition X into two sets S(1) and S(2) in order to minimize the value of ΣiΣ{u,v}⊂S(i)d(u,v). In this paper, we show an approximation scheme for this problem
  • Keywords
    approximation theory; computational complexity; graph theory; minimisation; pattern clustering; set theory; clustering; metric 2-clustering problem; metric spaces; minimization; set partitioning; sublinear-time approximation scheme; weighted graph; Clustering algorithms; Extraterrestrial measurements; Polynomials;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1999. 40th Annual Symposium on
  • Conference_Location
    New York City, NY
  • ISSN
    0272-5428
  • Print_ISBN
    0-7695-0409-4
  • Type

    conf

  • DOI
    10.1109/SFFCS.1999.814587
  • Filename
    814587
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3449993