摘要
对给定规模为ｎ的集合Ｓ，其每一个规模至多为ｋ的子集对应一个权．本文研究如何将Ｓ分为 个互不相交的规模至多为ｋ的子集且满足权和最大的问题．我们证明了该问题当ｋ＝２时是多项式时间可解的；当ｋ≥３时为ＮＰ－完全的；同时给出了一个Ｏ（ｎ￣（ｋ＋１））时间的启发式算法，所得到的解与最优解之比不小于１／ｋ．
Given a set S of size n, each of its subsets of size at most k is assigned a weight. The problem is to divide S into pairwise disjoint subsets, each of size at most k,such that the total weight is maximum. In this paper, the problem is proved to be polynomially solvable for k=2 and NP-complete for k≥3. Furthermore, we show that a bounded heuristic for k≥3 within a factor k from optimum can be computed in time O(n￣(k+1)).
出处
《高校应用数学学报（A辑）》
CSCD
北大核心
1994年第4期453-457,共5页
Applied Mathematics A Journal of Chinese Universities(Ser.A)
关键词
分拆
匹配
启发式算法
k子集分拆
Partition
NP-Complete
3-dimensional Matching Problem
Heuristics.
