| 带核集分划问题的一个线性1／7近似算法 |
| |
| 引用本文： | 何勇.带核集分划问题的一个线性1／7近似算法[J].高校应用数学学报(A辑),1997(4):467-474. |
| |
| 作者姓名： | 何勇 |
| |
| 作者单位： | 浙江大学应用数学系 |
| |
| 摘 要： | 设有整数集Ｓ＝｛ｒ１，ｒ２；ｐ１，ｐ２，…，ｐｎ｝，这里ｒｉ≥０，ｐｊ＞０（ｉ＝１，２；ｊ＝１，２，…，ｎ），寻找一个Ｓ的最优分划Ｐ＝（Ｓ＊１，Ｓ＊２）使得：（１）ｒｉ属于不同子集，（２）Ｓ＊１与Ｓ＊２中元素总和较大者尽可能地小．这是一个ＮＰ－完备问题，本文给出一个线性时间近似算法，它的近似界为８７．
|
| 关 键 词： | 带核集分划 近似算法 NP完备问题 集合分划 |
A LINEAR TIME 17 APPROXIMATE ALGORITHM FOR PARTITIONING PROBLEM WITH KERNEL SET |
| |
| He Yong.A LINEAR TIME 17 APPROXIMATE ALGORITHM FOR PARTITIONING PROBLEM WITH KERNEL SET[J].Applied Mathematics A Journal of Chinese Universities,1997(4):467-474. |
| |
| Authors: | He Yong |
| |
| Abstract: | |
| |
| Keywords: | Partition with Kernel Set Approximate Algorithm |
| 本文献已被 CNKI 维普 等数据库收录！ |
