10.3969/j.issn.1000-4424.2002.04.012
单背包问题的半定松弛算法
首先给出了单背包问题的秩1半定松弛规划,然后在此基础上提出了求解该问题的半定松弛随机算法KSSD.分析结果表明:(1)当σ>0.19时,算法KSSD的近似比就会超过0.27.(2)算法KSSD中的参数θ对某种大规模情形将不起作用.
背包问题、半定松弛、近似算法、组合优化
17
O221.7(运筹学)
国家重点基础研究发展计划973计划;国家自然科学基金19971078
2004-01-08(万方平台首次上网日期,不代表论文的发表时间)
共11页
460-470