标题： 最大最小和1 bounded 空间算法用于二进制包装问题 显示英文标题

标题： Max-Min and 1-Bounded Space Algorithms for the Bin Packing Problem

摘要： 在(1维)装箱问题中，我们需要将所有给定的物品装入容量为1的箱子中，使得非空箱子的数量最小。 Zhu~[Chaos, Solitons & Fractals 2016] 提出了一种近似算法$MM$，该算法首先按大小对物品序列进行非递增排序，然后反复地将剩余序列中尽可能多的最大物品先装入当前打开的单个箱子中，然后再尽可能多地将剩余序列中最小的物品装入该箱子中。 在本文中，我们证明了$MM$的渐近近似比最多为1.5。 接下来，我们专注于$MM$处于两个算法类的交集这一事实，即最大-最小算法和1-有界空间算法，我们全面分析了从这两个类中派生出的每个子类的理论性能界限。 我们的结果包括这两个类的交集的一个下限为1.25。 此外，我们将对算法类的理论分析扩展到基数约束的装箱问题。 显示英文摘要

摘要： In the (1-dimensional) bin packing problem, we are asked to pack all the given items into bins, each of capacity one, so that the number of non-empty bins is minimized. Zhu~[Chaos, Solitons \& Fractals 2016] proposed an approximation algorithm $MM$ that sorts the item sequence in a non-increasing order by size at the beginning, and then repeatedly packs, into the current single open bin, first as many of the largest items in the remaining sequence as possible and then as many of the smallest items in the remaining sequence as possible. In this paper we prove that the asymptotic approximation ratio of $MM$ is at most 1.5. Next, focusing on the fact that $MM$ is at the intersection of two algorithm classes, max-min algorithms and 1-bounded space algorithms, we comprehensively analyze the theoretical performance bounds of each subclass derived from the two classes. Our results include a lower bound of 1.25 for the intersection of the two classes. Furthermore, we extend the theoretical analysis over algorithm classes to the cardinality constrained bin packing problem.