单背包问题的半定松弛算法

• 作者: 姚恩瑜 陈峰
• 来源期刊: 高校应用数学学报A辑
• 学科: 数学
• 关键词: 背包问题 半定松弛 近似算法 组合优化
• 年，卷（期）: 2002,（4）
• 页码范围: 460-470
• 页数: 11页
• 分类号: O221.7
• 字数: 4127字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-4424.2002.04.012

摘要

首先给出了单背包问题的秩1半定松弛规划,然后在此基础上提出了求解该问题的半定松弛随机算法KSSD.分析结果表明:(1)当σ>0.19时,算法KSSD的近似比就会超过0.27.(2)算法KSSD中的参数θ对某种大规模情形将不起作用.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈峰	上海大学数学系	9	82	5.0	9.0
2	姚恩瑜	浙江大学数学系	17	117	5.0	10.0