Denser Packings Obtained in O(n log log n) Time
Denser Packings Obtained in O(n log log n) Time
复制标题
DOI：
10.1287/ijoc.1060.0192
复制
发表时间：
2007-07
期刊：
影响因子：
--
通讯作者：
David Pisinger
中科院分区：
文献类型：
--
作者：
David Pisinger
布局问题是将一组矩形包装成一个最小面积的外接矩形。由于很难直接在布局上进行优化，文献中已经提出了许多拓扑表示。其中最成功的是序列对表示法。与之前使用序列对的论文不同，我们没有使用相应的约束图，而是将序列解释为构造性算法中的包装顺序。生成的所有放置都是半归一化的，即，每个模块根据当前的包装轮廓尽可能地向左和向下移动。结果表明，这两种解释是等效的任何最小面积的位置，并为一个给定的序列对的新的解释结果在一个位置使用不超过约束图的解释。转换运行时间为O（nlog log n），并且能够处理模块位置上的各种约束。模拟退火框架的基础上的计算结果表明，该算法是能够显着改善的最佳解决方案的基准超大规模集成电路（VLSI）的电路设计问题，使用不到10秒的CPU时间。对于大的包装问题，它能迅速找到解决方案，浪费不超过3%-5%的空间。
The placement problem is that of packing a set of rectangles into a minimum-area enclosing rectangle. Since it is difficult to optimize directly on a placement, a number of topological representations have been presented in the literature. One of the most successful is the sequence pair representation. As opposed to previous papers using sequence pair, we do not make use of the corresponding constraint graph, but interpret the sequences as a packing order in a constructive algorithm. All placements generated are semi-normalized, i.e., each module is moved as far left and down as possible according to the current packing contour. It is shown that the two interpretations are equivalent for any minimum-area placement, and for a given sequence pair the new interpretation results in a placement using no more area than the constraint graph interpretation. The transformation runs in O(nlog log n) time and it is able to handle various constraints on the location of modules. Computational results based on a simulated-annealing framework show that the algorithm is able to improve significantly on the best found solutions for benchmark very large-scale integrated (VLSI) circuit design problems using less than ten seconds of CPU time. For large packing problems it is able to find solutions quickly that waste no more than 3%--5percnt; of the space.