在线背包问题的相关模型和算法分析

背包问题是经典的组合最优化问题之一，传统的背包问题只能解决事先给出物品信息的资源调配，而近几年在线背包问题是背包问题研究领域的重要分支之一。该理论对于解决现实生活中非确定条件下资源的分配有着重要的意义，比如网络应用中的关键字拍卖，广告显示等。本项目工作重点是研究在线背包的相关模型和算法分析，包括提出在线背包的五个新模型，即在线凸，凹，有偿，递增，递减背包模型，设计近似比（竞争比）为常数的在线算法并分别给出可行性分析，讨论相应模型在线算法竞争比的下界等。项目的目标是使得在线算法的近似比跟各自问题的下界尽量接近，以至于吻合。最后考虑进一步推广利用所提出的在线算法来解决在网络时代中新涌现的其它在线问题。

该项目所研究的在线背包问题, 是组合优化, 计算机理论,运筹领域中比较基本的问题，在网络关键字拍卖等有着重要应用。 三年来，本人对立项中的在线背包问题取得以下主要结果：.1：对于有偿在线背包问题，我们找到了一个上届和下届一致的在线算法，文章发表在国际重要期刊Algorithmica 2014;.2: 对于带凸函数在线背包问题，我们给出了一个上届世5/3的在线算法，文章发表在国际重要期刊Theoretical Computer Science 2014;.3：对于二维的背包问题，我们要给出近似比为1+\eps的快速近似算法，文章发表在Theoretical Computer Science 2013;.4:对于带凹函数的背包问题，我们给出上届和下届差是1的在线算法，文章正在投稿中。..因为背包问题和装箱问题，还有调度问题，它们之间有着很好的相关性，除了对在线背包问题的研究之外，我们也有计划外的产物，具体如下：.1：对三维strip packing问题,我们给出近似比为1.69103的渐进近似算法，该比值是目前最好的比值，文章发表在国际顶级期刊 SIAM Journal on computing2013；.2：对二维在线装箱问题我们给出了竞争比为2.55的在线算法，该算法也是目前最好的算法，文章发表在在国际顶级期刊ACM Transactions on Algorithms 2011；.3：另外对在线排序问题进行了研究，在Theoretical Computer Science，Information Processing Letters等期刊上发表了数篇文章。..总体上我们很好完成了立项中的问题，同时也额外的取得了计划外的结果。共发表SCI检索期刊文章13篇, EI检索文章20篇。.同时获得了2014年中国运筹学会的青年科技奖的提名奖。