装箱问题的理论与算法

项目名称： 装箱问题的理论与算法

项目编号： No.10971192

项目类型： 面上项目

立项/批准年度： 2010

项目学科： 数理科学和化学

项目作者： 张国川

作者单位： 浙江大学

项目金额： 23万元

中文摘要： 装箱（Bin Packing）是组合优化的一个经典问题。以其为基本模型构成的装箱问题类有强烈的实际背景和深刻的算法理论意义。本项目研究若干具体装箱问题的算法结构和性质，通过对带个数限制的在线装箱、元素有区间约束的装箱、二维带状装箱、一般费用下的装箱以及传感器安置等问题的深入探讨，刻画相应问题的内在特性以及可行装箱的充分条件和必要条件。利用这些条件分析和估计算法的上下界，试图在算法设计与分析的思想上有所突破。在此基础上取得重要算法结果。

中文关键词： 装箱；调度；近似算法；在线算法；机制设计

英文摘要：

英文关键词： Bin packing；Scheduling；Approximation algorithms；Online algorithms；Mechanism design