首页    期刊浏览 2024年11月05日 星期二
登录注册

文章基本信息

  • 标题:Hardness and Non-Approximability of Bregman Clustering Problems
  • 本地全文:下载
  • 作者:Marcel R. Ackermann ; Johannes Blömer ; Christoph Scholz
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2011
  • 卷号:2011
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:We prove the computational hardness of three k-clustering problems using an (almost) arbitrary Bregman divergence as dissimilarity measure: (a) The Bregman k-center problem, where the objective is to find a set of centers that minimizes the maximum dissimilarity of any input point towards its closest center, and (b) the Bregman k-diameter problem, where the objective is to minimize the maximum dissimilarity between pairs of points from the same cluster, and (c) the Bregman k-median problem, where the objective is to find a set of centers that minimizes the average dissimilarity of any input point towards its closest center. We show that solving these problems is NP-hard, and that it is even NP-hard to approximate a solution of (a) and (b) within a factor of (a) 3.32 and (b) 3.87, respectively. To obtain our results, we give a gap-preserving reduction from the Euclidean k-center (k-diameter, k-means) problem to the Bregman k-center (k-diameter, k-median) problem. This reduction combines the technique of Mahalanobis-similarity from Ackermann et al. (SODA '08) with a reduction already used by Chaudhuri and McGregor (COLT '08) to show the non-approximability of the Kullback-Leibler k-center problem, and a recent reduction given by Vattani to prove the NP-hardness of the Euclidean k-means problem.
  • 关键词:algorithmic learning theory, Bregman divergences, Clustering, Computational Complexity
国家哲学社会科学文献中心版权所有