-
题名带核箱覆盖问题的在线算法
被引量：1
- 1
-
-
作者
苏纯洁
姚恩瑜
-
机构
浙江大学数学系
-
出处
《运筹学学报》
CSCD
1999年第4期71-78,共8页
-
基金
国家重点基础研究专项经费资助
-
文摘
经典的箱覆盖问题是组合优化中一个著名的问题，并且得到了广泛的研究．本文主要讨论带核元的箱覆盖问题的复杂性和在线条件下的算法．指出了带核的箱覆盖问题是强ＮＰ－ｈａｒｄ的．给出了在不同的在线条件下可行算法渐近比的上界，指出仅在条件三下才存在渐近比好于０的在线算法，并给出了在此条件下一个渐近比为１／２的最好的在线算法。
-
关键词
复杂性
渐近比
组合优化
箱覆盖问题
在线算法
-
Keywords
kernal, complexity, worst-case bound.
-
分类号
O224
[理学—运筹学与控制论]
-
-
题名基于LIB的有色箱覆盖问题
- 2
-
-
作者
杨鼎强
-
机构
长沙理工大学计算机与通信工程学院
-
出处
《计算机工程与设计》
CSCD
北大核心
2008年第9期2269-2271,共3页
-
基金
湖南省教育厅科研基金项目(06C126)
-
文摘
提出了如下定义的受位置约束的有色箱覆盖问题,即在有色物品的箱覆盖过程中,要求重(长)的物品置于轻(短)的物品下方。该问题是一个新的组合优化问题,来源于多处理器任务调度。给出一个求解该问题的局内近似算法KC-LIBFF算法,分析其最坏情况渐进性能比为0,并给出了相应的实验结果;进一步对求解该问题的局内算法性能比的下界进行了讨论。
-
关键词
箱覆盖问题
调度问题
组合优化
近似算法
最坏情况渐进性能比
-
Keywords
bin-covering problem
scheduling
combinational optimization
approximation algorithm
worst-case performance ratio
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-
-
题名箱覆盖问题的半定松驰算法
- 3
-
-
作者
陈峰
姚恩瑜
-
机构
浙江大学数学系
-
出处
《运筹学学报》
CSCD
北大核心
2002年第2期85-96,共12页
-
基金
国家重点基础研究专项经费资助
国家自然科学基金(19971078).
-
文摘
箱覆盖问题是NP困难问题中的经典问题,得到了广泛地研究.九十年代以来,半定松驰策略被用来求解组合优化问题,取得了很好的结果[13].本文首次给箱覆盖问题的半定松驰算法.算法的理论分析结果表明它适合于求解大规模的箱覆盖问题.
-
关键词
半定松驰算法
箱覆盖问题
近似算法
组合优化
-
Keywords
bin covering problem, semidefinite relaxation, Approximation algo-rithm, combinatorial optimization.
-
分类号
O224
[理学—运筹学与控制论]
-
-
题名带拒绝箱覆盖问题的局内算法
- 4
-
-
作者
杨鼎强
蒋加伏
-
机构
长沙理工大学计算机与通信工程学院
-
出处
《计算技术与自动化》
2007年第2期31-33,共3页
-
基金
湖南省教育厅科技项目资助(No.06C126)
-
文摘
作为对装箱覆盖问题的推广,提出带拒绝的装箱覆盖问题。设有许多等长的一维箱子,给定一个物品集,每个物品有两个参数:长度和费用。物品可以放入箱子也可被拒绝放入箱子,每个物品只准放入一只箱子中,每只箱子中的物品容量总和至少为箱子容量,一旦箱子中的物品长度达到要求则需启用新箱。如果物品被放入箱中,则产生费用。该问题是一个新的组合优化问题,在内部互联网信息管理等问题中有着广泛的应用背景。给出一个求解该问题的局内近似算法C-FF,分析其最坏情况渐近性能比为1/2,并给出了相应的实验结果。
-
关键词
箱覆盖问题
近似算法
最坏情况渐近性能比
因特网通信
信息管理
-
Keywords
bin covering problem
approximation algorithm
asymptotic worst- case performance ratio
internet communication
information management
-
分类号
TP393
[自动化与计算机技术—计算机应用技术]
-
