论文标题
用分区曲线填料可以在$ O（OPT）$ bins中近似
Bin Packing with Partition Matroid can be Approximated within $o(OPT)$ Bins
论文作者
论文摘要
我们考虑了分区矩阵约束的垃圾箱包装问题。 The input is a set of items of sizes in $(0,1]$, and a partition matroid over the items. The goal is to pack all items in a minimum number of unit-size bins, such that each bin forms an independent set in the matroid. The problem is a generalization of both Group Bin Packing and Bin Packing with Cardinality Constraints. Bin Packing with Partition Matroid naturally arises in resource allocation to ensure fault tolerance and security,在收获计算能力中，我们的主要结果是将项目包装在$ opt + o（opt）$ bin中的多项式算法，其中opt是包装给定实例的最小垃圾桶。我们的方法是基于对问题的配置公式的解决方案，这是一个新颖的原型观点。
We consider the Bin Packing problem with a partition matroid constraint. The input is a set of items of sizes in $(0,1]$, and a partition matroid over the items. The goal is to pack all items in a minimum number of unit-size bins, such that each bin forms an independent set in the matroid. The problem is a generalization of both Group Bin Packing and Bin Packing with Cardinality Constraints. Bin Packing with Partition Matroid naturally arises in resource allocation to ensure fault tolerance and security, as well as in harvesting computing capacity. Our main result is a polynomial-time algorithm that packs the items in $OPT + o(OPT)$ bins, where OPT is the minimum number of bins required for packing the given instance. This matches the best known result for the classic Bin Packing problem up to the function hidden by o(OPT). As special cases, our result improves upon the existing APTAS for Group Bin Packing and generalizes the AFTPAS for Bin Packing with Cardinality Constraints. Our approach is based on rounding a solution for a configuration-LP formulation of the problem. The rounding takes a novel point of view of prototypes in which items are interpreted as placeholders for other items and applies fractional grouping to modify a fractional solution (prototype) into one having nice integrality properties.
