高校应用数学学报A辑
高校應用數學學報A輯
고교응용수학학보A집
APPLIED MATHEMATICS A JOURNAL OF CHINESE UNIVERSITIES
2002年
4期
460-470
,共11页
背包问题%半定松弛%近似算法%组合优化
揹包問題%半定鬆弛%近似算法%組閤優化
배포문제%반정송이%근사산법%조합우화
首先给出了单背包问题的秩1半定松弛规划,然后在此基础上提出了求解该问题的半定松弛随机算法KSSD.分析结果表明:(1)当σ>0.19时,算法KSSD的近似比就会超过0.27.(2)算法KSSD中的参数θ对某种大规模情形将不起作用.
首先給齣瞭單揹包問題的秩1半定鬆弛規劃,然後在此基礎上提齣瞭求解該問題的半定鬆弛隨機算法KSSD.分析結果錶明:(1)噹σ>0.19時,算法KSSD的近似比就會超過0.27.(2)算法KSSD中的參數θ對某種大規模情形將不起作用.
수선급출료단배포문제적질1반정송이규화,연후재차기출상제출료구해해문제적반정송이수궤산법KSSD.분석결과표명:(1)당σ>0.19시,산법KSSD적근사비취회초과0.27.(2)산법KSSD중적삼수θ대모충대규모정형장불기작용.
