若干装箱问题模型的研究

Bin Packing is one of the classic problems in combinatorial optimization,.being witnessed the development of approximation algorithms and online algorithms..This problem has a wide range of applications, such as memory allocation within the computer field,. the cloud platform game resource allocation and so on. And in recent years, on the packing problem, the new results are endless. .Around the new results, the model emerging, we explore seven new models in this project from the three aspects: bin packing game, one-dimensional bin packing, multi-dimensional bin packing. For a one-dimensional, multi-dimensional packing problem .we focus on designing and analazying approximation algorithms and online algorithms. .For bin packing game, we investigate the ratio between the worst Nash Equilibrim and the social optimum.

装箱是经典组合优化问题之一, 该问题的研究见证了近似算法和在线算法的发展历程。.该问题有着广泛的应用，比如计算机领域内存分配，云平台上游戏资源的分配等等。.而且近几年关于装箱问题的研究比较热，新的结果层出不穷。围绕新出现的结果和模型，.本项目从博弈，一维，多维，三个不同的角度探索装箱问题的七个新模型。.对于一维，多维装箱问题，本项目设计和分析相应的近似算法和在线算法。.对博弈装箱问题，本项目考察最坏均衡的解和社会最优解比值的大小。

装箱是经典组合优化问题之一, 该问题的研究见证了近似算法和在线算法的发展历程。.该问题有着广泛的应用，比如计算机领域内存分配，云平台上游戏资源的分配等等。.该项目重要结果如下：共发表11篇文章，其中CCF A 类期刊1篇 ，CCF B类期刊6篇等。.具体如下：..1：给出了一维装箱问题和条形装箱的对应关系，文章发表在CCF（计算机协 会）推荐的A类期刊中。.2：研究了带缓冲的在线装箱问题，就是物品可以暂时放在一定容量的缓冲中，如果.缓冲满了，就必须放到一定规格的箱子中，目标是在输入结束时，最小化箱子的个数。.我们改进了前人的竞争比的上下界，文章发表在期刊： Journal of Combinatorial Optimization。.3：研究了带运输时间的2台流水调度，就是工件先在2台流水机器上加工，然后.被一台运输车运输到目的地。当每次最多只能运输常数2个物品时，前人证明是一般的Np难。我们进一步证明该问题为强Np-hard问题，.文章发表在期刊：Theoretical Computer Science CCF（计算机协 会）推荐的B类期刊中 。.4：研究了博弈下的在线装箱问题，就是物品是博弈的参与者，它可以选择去哪个箱.子，如果有空间的话。我们证明了当效用矩阵是对称的话，该博弈一定存在纳什均衡，并分析了几种特定条件下的效用矩阵，给出常数.的PoA. 文章发表在期刊： Algorithmica 80(5): 1534-1555 (2018)(CCF B类期刊) （算法方面国家顶级期刊）。.5：研究了凹函数下在线背包问题，给出了该问题的上下界，文章发布在Theoretical Computer Science CCF推荐的B类期刊中。.6： 研究了违约需要赔付的在线背包问题，违约赔付跟违约的个数成比例的前提下，当物品大小和价值成比例时，我们给了最优的在线算法，.文章发布在Theory of Computing Systems CCF B 类期刊。