| 关于最大权k－子集分拆问题 |
| |
| 引用本文： | 徐寅峰,刘自成.关于最大权k－子集分拆问题[J].高校应用数学学报(A辑),1994(4). |
| |
| 作者姓名： | 徐寅峰 刘自成 |
| |
| 作者单位： | 西安交通大学，中国科学院 |
| |
| 摘 要： | 对给定规模为ｎ的集合Ｓ，其每一个规模至多为ｋ的子集对应一个权．本文研究如何将Ｓ分为 个互不相交的规模至多为ｋ的子集且满足权和最大的问题．我们证明了该问题当ｋ＝２时是多项式时间可解的；当ｋ≥３时为ＮＰ－完全的；同时给出了一个Ｏ（ｎ￣（ｋ＋１））时间的启发式算法，所得到的解与最优解之比不小于１／ｋ．
|
| 关 键 词： | 分拆，NP－完全，3维匹配问题，启发式算法． |
ON MAXIMUM WEIGHT K-SUBSET PARTITION PROBLEMS |
| |
| Xu Yinfeng, Liu Zicheng.ON MAXIMUM WEIGHT K-SUBSET PARTITION PROBLEMS[J].Applied Mathematics A Journal of Chinese Universities,1994(4). |
| |
| Authors: | Xu Yinfeng Liu Zicheng |
| |
| Abstract: | |
| |
| Keywords: | Partition NP-Complete 3-dimensional Matching Problem Heuristics |
| 本文献已被 CNKI 等数据库收录！ |
