湖南大学学报（自然科学版）
湖南大學學報（自然科學版）
호남대학학보（자연과학판）
JOURNAL OF HUNAN UNIVERSITY(NATURAL SCIENCES EDITION)
2008年
2期
77-79
,共3页
近似算法%箱子覆盖问题%组合优化%渐近性能比
近似算法%箱子覆蓋問題%組閤優化%漸近性能比
근사산법%상자복개문제%조합우화%점근성능비
提出了一种有实际背景的最小费用箱子覆盖问题──每个物品有长度和费用2个参数.针对局外最小费用箱子覆盖问题,给出了一个求解该问题的最坏情况渐近性能比为1/2算法C-FF1.同时给出了一个求解该问题的局内算法C-FF2,其绝对性能比为1/2,并证明了不存在绝对性能比大于1的算法.
提齣瞭一種有實際揹景的最小費用箱子覆蓋問題──每箇物品有長度和費用2箇參數.針對跼外最小費用箱子覆蓋問題,給齣瞭一箇求解該問題的最壞情況漸近性能比為1/2算法C-FF1.同時給齣瞭一箇求解該問題的跼內算法C-FF2,其絕對性能比為1/2,併證明瞭不存在絕對性能比大于1的算法.
제출료일충유실제배경적최소비용상자복개문제──매개물품유장도화비용2개삼수.침대국외최소비용상자복개문제,급출료일개구해해문제적최배정황점근성능비위1/2산법C-FF1.동시급출료일개구해해문제적국내산법C-FF2,기절대성능비위1/2,병증명료불존재절대성능비대우1적산법.
