Denser Packings Obtained in O(n log log n) Time

References

• Berkey J. O., Wang P. Y. Two dimensional finite bin packing algorithms. J. Oper. Res. Society (1987) 38:423–429Crossref, Google Scholar
• Chang Y. C., Chang Y. W., Wu G. M., Wu S. W. B*-trees: A new representation for non-slicing floorplans. Proc. 37th ACM/IEEE Conf. Design Automation (2000) Los Angeles, CA:458–463Crossref, Google Scholar
• Christofides N., Whitlock C. An algorithm for two-dimensional cutting problems. Oper. Res. (1977) 25:30–44Link, Google Scholar
• Guo P. N., Cheng C. K., Yoshimura T. An O-tree representation of non-slicing floorplans and its applications. Proc. 36th ACM/IEEE Conf. Design Automation (1999) New Orleans, LA:268–273Crossref, Google Scholar
• Hong X., Huang G., Cai Y., Gu J., Dong S., Cheng C.-K., Gu J. Corner block list: An effective and efficient topological representation of non-slicing floorplan. Internat. Conf. Computer-Aided Design (2000) San Jose, CA:8–12Google Scholar
• Iori M., Martello S., Monaci M., Pardalos P. M., Korotkikh V. Metaheuristic algorithms for the strip packing problem. Optimization and Industry: New Frontiers (2003) (Kluwer Academic Publishers, Dordrecht, The Netherlands) 159–179Crossref, Google Scholar
• Korf R. E. Optimal rectangle packing: New results. 14th Internat. Conf. Automated Planning and Scheduling, Whistler (2004) British Columbia, CanadaGoogle Scholar
• Martello S., Vigo D. Exact solution of the two-dimensional finite bin packing problem. Management Sci. (1998) 44:388–399Link, Google Scholar
• Martello S., Monaci M., Vigo D. An exact approach to the strip-packing problem. INFORMS J. Comput. (2003) 15:310–319Link, Google Scholar
• Martello S., Pisinger D., Vigo D. The three-dimensional bin packing problem. Oper. Res. (2000) 48:256–267Link, Google Scholar
• MCNC (2001) . Floorplan benchmark tests, http://www.cse.ucsc.edu/research/surf/GSRC/MCNCbench.htmlGoogle Scholar
• Murata H., Fujiyoshi K., Nakatake S., Kajitani Y. VLSI module placement based on rectangle-packing by the sequence pair. IEEE Trans. Comput. Aided Design Integrated Circuits Systems (1996) 15:1518–1524Crossref, Google Scholar
• Pang Y., Cheng C. K., Yoshimura T. An enhanced perturbing algorithm for floorplan design using the O-tree representation. Proc. Internat. Sympos. Physical Design (2000) San Diego, CA:168–173Crossref, Google Scholar
• Takahashi T. An algorithm for finding a maximum-weight decreasing sequence in a permutation, motivated by rectangle packing problem. (1996) . IEICE Technical Report VLD96, 201, 31–35, Institute of Electronics, Information and Communication Engineers, Tokyo, JapanGoogle Scholar
• Tang X., Wong D. F. FAST-SP: A fast algorithm for block placement based on sequence pair. Proc. Asia and South Pacific Design Automation Conf. (2001) Yokohama, Japan:521–526Crossref, Google Scholar
• Tang X., Tian R., Wong D. F. Fast evaluation of sequence pair in block placement by longest common subsequence computation. Proc. Design, Automation and Test in Europe (DATE2000) (2000) Paris, France:106–111Crossref, Google Scholar
• van Emde Boas P. Preserving order in a forest in less than logarithmic time and linear space. Inform. Processing Lett. (1977) 6:80–82Crossref, Google Scholar