...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of applied and industrial mathematics >An Exact Pseudopolynomial Algorithm for a Problem of the Two-Cluster Partitioning of a Set of Vectors
【24h】

An Exact Pseudopolynomial Algorithm for a Problem of the Two-Cluster Partitioning of a Set of Vectors

机译：一组向量的两簇划分问题的精确伪多项式算法

获取原文
获取原文并翻译 | 示例
   

获取外文期刊封面封底 >>

       
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We consider the strongly NP-hard problem of partitioning a set of Euclidean vectors into two clusters of given sizes so as to minimize the sum of the squared distances from the elements of the clusters to their centers. It is assumed that the center of one of the clusters is unknown and determined as the average value over all vectors in the cluster. The center of the other cluster is the origin.We prove that, for a fixed dimension of the space, the problem is solvable in polynomial time. We also present and justify an exact pseudopolynomial algorithm in the case of integer components of the vectors.
机译：我们考虑了将一组欧几里得向量划分为给定大小的两个簇的强烈NP难题，以最小化从簇元素到其中心的平方距离之和。假设群集之一的中心是未知的，并确定为群集中所有向量的平均值。另一个簇的中心是原点。我们证明，对于空间的固定维数，该问题可以在多项式时间内解决。在向量的整数分量的情况下，我们还提出并证明了精确的伪多项式算法。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号