论文部分内容阅读
研究有元素类型约束且每个元素权重为正数的k-集合划分问题，元素类型约束指k-划分后每个集合所包含的元素的类型均不同．该问题是对k-划分问题（k-partitioning problem）的一个拓展，在一人可拥有多技能执照的行业有广泛的应用背景．提出基于LPT算法思想的贪婪算法，并得出以下结论：k≤2，该算法给出最优解：k〉2，最坏情况下的性能比为2-m^-1，这里m指待分配集合的数量．