...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of applied and industrial mathematics >A Fully Polynomial-Time Approximation Scheme for a Sequence 2-Cluster Partitioning Problem
【24h】

A Fully Polynomial-Time Approximation Scheme for a Sequence 2-Cluster Partitioning Problem

机译：序列2聚类分配问题的完全多项式时间逼近方案

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

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

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

摘要

We consider a strongly NP-hard problem of partitioning a finite sequence of points in Euclidean space into the two clustersminimizing the sum over both clusters of intra-cluster sums of squared distances from the clusters elements to their centers. The sizes of the clusters are fixed. The centroid of the first cluster is defined as the mean value of all vectors in the cluster, and the center of the second cluster is given in advance and equals 0. Additionally, the partition must satisfy the restriction that for all vectors in the first cluster the difference between the indices of two consequent points from this cluster is bounded from below and above by some given constants.We present a fully polynomial-time approximation scheme for the case of fixed space dimension.
机译：我们考虑了一个强NP难问题，即将欧几里德空间中的有限点序列划分为两个簇，以最小化两个簇中簇内元素到其中心的平方距离之和。群集的大小是固定的。第一个聚类的质心定义为该聚类中所有向量的平均值，第二个聚类的中心预先给出且等于0。此外，该分区必须满足以下条件：对于第一个聚类中的所有向量该簇的两个结果点的索引之间的差值由上下给定一些常数。对于固定空间维数，我们提出了一个完全多项式时间近似方案。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号