|
|||||
|
|
| 单背包问题的半定松弛算法 | |
| 引用本文： | 陈峰,姚恩瑜. 单背包问题的半定松弛算法[J]. 高校应用数学学报(A辑), 2002, 17(4): 460-470 |
| 作者姓名： | 陈峰 姚恩瑜 |
| 作者单位： | 上海大学数学系,上海,200436;浙江大学,数学系,浙江,杭州,310027 |
| 基金项目： | 国家重点基础研究专项经费资助;国家自然科学基金(19971078) |
| 摘 要： | 首先给出了单背包问题的秩1半定松驰规划,然后在此基础上提出了求解该问题的半定松驰随机算法KSSD。分析结果表明：（1）当σ＞0.19时,算法KSSD的近似比就会超过0.27。（2）算法KSSD中的参数θ对某种大规模情形将不起作用。 |
| 关 键 词： | 背包问题 半定松弛 近似算法 组合优化 |
| 文章编号： | 1000-4424(2002)04-0460-11 |
| 修稿时间： | 2002-01-16 |
Semidefinite relaxation of knapsack problem |
|
| Abstract: | |
| Keywords: | |
| 本文献已被 维普 万方数据 等数据库收录！ | |