摘要
首先给出了单背包问题的秩 1半定松弛规划 ,然后在此基础上提出了求解该问题的半定松弛随机算法 KSSD.分析结果表明 :(1 )当σ>0 .1 9时 ,算法KSSD的近似比就会超过 0 .2 7.(2 )算法
Knapsack is a classic NP\|hard problem.In the last ten years,semi\|definite relaxation technique was successfully employed to solve some combinatorial optimization problems.The paper presents the rank one semi\|definite relaxation programming(SKSSA)of knapsack problem.Based on this programming, a randomized approximation algorithm KSSD to solve knapsack problem is constructed.The following two results are obtained through analysing the algorithm:(1)If σ >0.19,the approximation ratio of the KSSD exceeds 0.27;(2) The parameter θ in algorithm KSSD is likely to be invalid for a subproblem of large scale. $$$$
出处
《高校应用数学学报（A辑）》
CSCD
北大核心
2002年第4期460-470,共11页
Applied Mathematics A Journal of Chinese Universities(Ser.A)
基金
国家重点基础研究专项经费资助
国家自然科学基金 (1 9971 0 78)
关键词
背包问题
半定松驰
近似算法
组合优化
knapsack problem
semidefinite relaxation
approximation algorithm
combinatorial optimization
