多维背包、多维装箱的近似算法，机制设计及其应用

The knapsack problem and the bin packing problem both are classical combinatorial optimization problems. With the developing of Internet and cloud computing, and the economic theory applied in the algorithm design area, it arises great challenges for the classical combinatorial optimization problems in this new computing environment. This project will explore the theoretical study on approximation algorithms, algorithmic mechanism designs for multidimensional bin packing, maximum multidimensional knapsack, minimum multidimensional knapsack problems, and their applications. The multidimensional bin packing problem arises in the resource provision of virtual machines in cloud computing. The maximum multidimensional knapsack problem arises in applications of mechanism design on the resource auction in a cloud platform. The minimum knapsack problem can be applied in the demand response of colocation date centers and the greenhouse gases emissions trading systems. A key problem we need to investigate is how to get a balance between truthfulness, computational complexity, and the approximation ratio of a mechanism. This project aims to investigate fundamental theories among the proposed practical problems, and finally solve the practical problems with the helping of theoretical results. Thus, this project is expected to make a number of transformative theoretical contributions and enrich the research on the area of operations research, theoretical computer science, and economics. This project is expected to provide benefits in reducing energy consumption of data centers and in efficient resource provisioning of cloud computing platforms.

背包问题和装箱问题都是组合优化的核心问题。随着互联网和云计算的发展，以及经济学理论在算法设计方面的交叉渗透，典型的组合优化问题在新型的计算模式下涌现出新的挑战。本项目拟就多维装箱问题，最大化多维背包问题，和最小化多维背包问题开展近似算法和算法机制设计的理论研究及其具体应用研究。多维装箱问题可应用于云平台虚拟机的资源配置和机制设计。最大化多维背包问题可应用于云计算平台各租户之间的资源拍卖的机制设计。最小化背包问题可应用于合租数据中心的电力需求响应机制设计和温室气体排放交易的机制设计。本项目主要研究如何在机制的诚实性，算法的计算效率，以及可近似性之间寻找最佳的平衡。本项目通过对基于实际应用的问题进行理论研究，然后用研究成果来指导解决实际问题。并旨在丰富运筹学、理论计算机科学、经济学交叉领域的相关研究。本项目的研究成果期望在数据中心的节能、云平台的资源有效配置方面作出贡献。

随着互联网和云计算的发展，以及经济理论在算法设计方面的交叉渗透，典型的组合优化问题在新型计算模式下涌现出新的挑战。本项目主要研究这些新的挑战，包括多维装箱问题、多维背包问题、最小化背包问题的理论研究和具体应用研究。主要研究成果如下：.机制设计方面：.1.提出了装箱问题的诚实机制。本项目首先提出了装箱问题的机制设计模型。证明了装箱算法如果满足单调性并且相应的支付算法是关键阀值付费既可以获得诚实机制。同时，我们证明了任意的装箱算法在单调性的假设下近似比最少为2，且Next Fit算法近似比为2. 本研究可应用于云计算平台的多维资源拍卖、箱子拍卖。.2.最小化背包及在电力需求响应方面的机制研究。Zhang等INFOCOM2015在合租数据中心需求响应中给出了近似比为2的随机机制。本项目给出了确定性完全近似多项式方案（FPTAS）诚实机制。本研究可应用于数据中心紧急需求响应。.3.研究机制设计中相关因素对机制的影响。研究数字化局中人的偏好，异构的效益函数，非线性的社会效益等在线上设施选址中的机制设计。.近似算法方面：.1.研究2维可变形装箱问题，将其刻画为可扩展并行任务调度。我们给出了常数竞争比的在线算法，并且任何的不可变装箱算法可以转换成我们的算法且能控制竞争比。.2.研究背包、排序问题的规划中约束矩阵为低秩的问题。证明秩为3的排序问题是APX－困难，从而解决了Bhaskara 等在SODA 2013所提出了公开问题。我们还提供了一个参数算法（FPT可解），同时也证明了在ETH猜想的假设下，所给出的参数算法是最优的。.3.研究背包问题相关的中断网络中的恶意传播问题，即设计挑选k个点的算法，通过抽样，并证明大概率情况下算法的近似比为0.4685。.本项目预期发表国际期刊或者国际会议论文10篇。目前，我们已经发表的论文有13篇论文（期刊8篇，国际会议5篇）。其中期刊有IEEE Transaction on Mobile Computing, Theoretical Computer Science，Discrete Applied Mathematics, Journal of Scheduling, Journal of Combinatorial Optimization; 国际会议包括 INFOCOM, ICDE, STACS, COCOON,COCOA等。