A new lower bound for online strip packing
| Autor: | Yanling Mao, Guosong Yu, Jiaoliao Xiao |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
021103 operations research
Information Systems and Management General Computer Science Competitive analysis 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology Management Science and Operations Research Strip packing 01 natural sciences Upper and lower bounds Industrial and Manufacturing Engineering Combinatorics Square packing in a square Strip packing problem 010201 computation theory & mathematics Modeling and Simulation Online algorithm Rotation (mathematics) Mathematics |
| Zdroj: | European Journal of Operational Research. 250:754-759 |
| ISSN: | 0377-2217 |
| DOI: | 10.1016/j.ejor.2015.10.012 |
| Popis: | In this paper, we consider the online strip packing problem, in which a list of online rectangles has to be packed without overlap or rotation into a strip of width 1 and infinite length so as to minimize the required height of the packing. We derive a new improved lower bound of (3+5)/2≈2.618 for the competitive ratio for this problem. This result improves the best known lower bound of 2.589. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect