Revisiting Chazelle's Implementation of the Bottom-Left Heuristic: A Corrected and Rigorous Analysis
Stefan Michel
条形包装问题是一个经典的优化问题,其中一组矩形必须打包,没有重叠,成固定宽度和无限高度的条带,同时最小化包装的总高度。 对这个问题的一种简单而广泛研究的方法是左下角。 它包括迭代地将每个矩形置于给定的顺序中,在条带中的最低可行位置,并在领带的情况下,在最左边的位置。 由于其简单性和良好的经验性能,这种方法论被广泛应用于实际应用中。 这种启发式方法的最有效率的实现是由Chazelle在1983年提出的,需要O(n^2)时间和空间来放置n矩形。 然而,尽管查泽尔的原始描述在很大程度上是正确的,但它省略了几个正式的细节。 此外,我们的分析揭示了原始运行时分析的一个关键缺陷,在某些情况下,该 Ω(n^3) 运行时间会导致Ω(n^3)。 在这一发现的激励下,本文对实施进行了严格和纠正的介绍,解决了不精确的论点并解决了已识别的缺陷。 由此产生的分析建立了Chazelle实施的正式验证版本,并证实了其二次时间复杂性。
The Strip Packing Problem is a classical optimization problem in which a given set of rectangles must be packed, without overlap, into a strip of fixed width and infinite height, while minimizing the total height of the packing. A straightforward and widely studied approach to this problem is the Bottom-Left Heuristic. It consists of iteratively placing each rectangle in the given order at the lowest feasible position in the strip and, in case of ties, at the leftmost of those. Due to its simpli...
