论文标题
eptas，可拆分垃圾箱的双重包装与基数约束
EPTAS for the dual of splittable bin packing with cardinality constraint
论文作者
论文摘要
考虑的问题是具有基数约束的可分解垃圾箱。它是垃圾箱包装问题的一种变体，其中允许项目分为零件，但每个垃圾箱中的零件数最多是给定的上限。在文献中已经研究了两个具有基数约束的可分解垃圾箱包装的版本。在这些变体中，我们考虑了双重的，其中目的是在包装（可能是分数）将项目包装到给定的垃圾箱时最小化最大垃圾箱的大小。当基数上限是输入的一部分时，我们将显示出双重问题的EPTA。这个结果回答了爱泼斯坦，莱文和范·斯蒂提出的一个公开问题。
The problem considered is the splittable bin packing with cardinality constraint. It is a variant of the bin packing problem where items are allowed to be split into parts but the number of parts in each bin is at most a given upper bound. Two versions of the splittable bin packing with cardinality constraint have been studied in the literature. Among these variants we consider the dual one where the objective is to minimize the maximum bin size while packing (may be fractional) the items to a given set of bins. We exhibit an EPTAS for the dual problem when the cardinality upper bound is part of the input. This result answers an open question raised by Epstein, Levin, and van Stee.
