Performance Bound for Bottom-Left Guillotine Packing of Rectangles

Autor:	Mahesh Girkar, Bruce MacLeod, Robert N. Moll
Rok vydání:	1992
Předmět:	Combinatorics Marketing Operations research Cutting stock problem Strategy and Management Management Science and Operations Research Bin Mathematics Management Information Systems
Zdroj:	The Journal of the Operational Research Society. 43:169
ISSN:	0160-5682
DOI:	10.2307/2583360
Popis:	In this article we show that bottom-left guillotine placement of rectangles ordered by decreasing width in a fixed-width bin is not more than three times the height of an optimal placement. This bound is also true for bottom-left placement of rectangles without the guillotine constraints. Thus, bottom-left guillotine placement in which rectangles are ordered by decreasing width has the same worst case performance bound as bottom-left placement of rectangles without guillotine constraints.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bbd29dfb98044001251b07a3ac647e41 https://doi.org/10.2307/2583360 Zobrazit plný text záznamu Full text from SpringerLink