项目简介
项目名称
在线背包问题的相关模型和算法分析
项目批准号
11101065
学科分类
A011202
数理科学部
_数学
_运筹学
_组合最优化
资助类型
数理科学
负责人
韩鑫
依托单位
大连理工大学
批准年份
2011
起止时间
201201-201412
批准金额
24.00万元
摘要
背包问题是经典的组合最优化问题之一，传统的背包问题只能解决事先给出物品信息的资源调配，而近几年在线背包问题是背包问题研究领域的重要分支之一。该理论对于解决现实生活中非确定条件下资源的分配有着重要的意义，比如网络应用中的关键字拍卖，广告显示等。本项目工作重点是研究在线背包的相关模型和算法分析，包括提出在线背包的五个新模型，即在线凸，凹，有偿，递增，递减背包模型，设计近似比（竞争比）为常数的在线算法并分别给出可行性分析，讨论相应模型在线算法竞争比的下界等。项目的目标是使得在线算法的近似比跟各自问题的下界尽量接近，以至于吻合。最后考虑进一步推广利用所提出的在线算法来解决在网络时代中新涌现的其它在线问题。
评论区 (0)
#插入话题
