We consider a known variant of bin packing called {\it cardinality constrained bin packing}, also called {\it bin packing with cardinality constraints} (BPCC). In this problem, there is a parameter k\geq 2, and items of rational sizes in [0,1] are to be packed into bins, such that no bin has more than k items or total size larger than 1. The goal is to minimize the number of bins. A recently introduced concept, called the price of clustering, deals with inputs that are presented in a way that they are split into clusters. Thus, an item has two attributes which are its size and its cluster. The goal is to measure the relation between an optimal solution that cannot combine items of different clusters into bins, and an optimal solution that can combine items of different clusters arbitrarily. Usually the number of clusters may be large, while clusters are relatively small, though not trivially small. Such problems are related to greedy bin packing algorithms, and to batched bin packing, which is similar to the price of clustering, but there is a constant number of large clusters. We analyze the price of clustering for BPCC, including the parametric case with bounded item sizes. We discuss several greedy algorithms for this problem that were not studied in the past, and comment on batched bin packing.
翻译：我们考虑的是已知的称为 ~ 基点限制 bin bin 包装的变式, 称为 ~ 基点限制 bin 包装 } (BPCC) 。 在这个问题中, 存在一个参数 k\geq 2, 并且 [ 0, 1] 中合理大小的项目将被包装在垃圾桶中, 这样, 任何垃圾桶都不超过 k 项或总大小大于 1 。 目标是最大限度地减少垃圾箱的数量 。 最近推出的一个概念, 叫做 集群的价格, 处理以它们分成组的方式展示的投入。 因此, 一个项目有两个属性, 即 大小和组群。 目标是测量一个不能将不同组的物品合并到垃圾箱中的最佳解决方案, 和一个可以任意将不同组项合并的最佳解决方案之间的关系。 通常, 集组的数量可能很大, 虽然组群并不小于1 。 这些问题与贪婪的 bin 包装算法有关, 和分批的包装包件包装方法相似, 但有一个不变的大型组群。 我们分析了 BPC C 的组集的价格, 包括不固定式的包装的容器, 我们研究过一些 的包装的容器 。
相关内容
微信扫码咨询专知VIP会员