Strip packing problem

An instance $I\; =\; (\backslash mathcal\{I\},W)$ of the strip packing problem consists of a strip with width $W\; =\; 1$ and infinite height, as well as a set $\backslash mathcal\{I\}$ of rectangular items.

Each item $i\; \backslash in\; \backslash mathcal\{I\}$ has a width $w\_i\; \backslash in\; (0,1]\; \backslash cap\; \backslash mathbb\{Q\}$ and a height $h\_i\; \backslash in\; (0,1]\; \backslash cap\; \backslash mathbb\{Q\}$.

A packing of the items is a mapping that maps each lower-left corner of an item $i\; \backslash in\; \backslash mathcal\{I\}$ to a position $(x\_i,y\_i)\; \backslash in\; ([0,1-w\_i]\; \backslash cap\; \backslash mathbb\{Q\})\; \backslash times\; \backslash mathbb\{Q\}\_\{\backslash geq\; 0\}$ inside the strip.

An inner point of a placed item $i\; \backslash in\; \backslash mathcal\{I\}$ is a point from the set .

Two (placed) items overlap if they share an inner point.

The height of the packing is defined as $\backslash max\; \backslash \{y\_i+h\_i\; |\; i\; \backslash in\; \backslash mathcal\{I\}\backslash \}$.

The objective is to find an overlapping-free packing of the items inside the strip while minimizing the height of the packing.

This definition is used for all polynomial time algorithms. For pseudo-polynomial time and FPT-algorithms, the definition is slightly changed for the simplification of notation. In this case, all appearing sizes are integral. Especially the width of the strip is given by an arbitrary integer number larger than 1. Note that these two definitions are equivalent.

There are several variants of the strip packing problem that have been studied. These variants concern the objects' geometry, the problem's dimension, the rotateability of the items, and the structure of the packing.{{cite web |last1=Neuenfeldt Junior |first1=Alvaro Luiz |title=The Two-Dimensional Rectangular Strip Packing Problem |url=https://repositorio-aberto.up.pt/bitstream/10216/109367/2/234741.pdf |id=10820228}}

Geometry: In the standard variant of this problem, the set of given items consists of rectangles.

In an often considered subcase, all the items have to be squares. This variant was already considered in the first paper about strip packing.

Additionally, variants where the shapes are circular or even irregular have been studied. In the latter case, it is referred to as irregular strip packing.

Dimension:

When not mentioned differently, the strip packing problem is a 2-dimensional problem. However, it also has been studied in three or even more dimensions. In this case, the objects are hyperrectangles, and the strip is open-ended in one dimension and bounded in the residual ones.

Rotation: In the classical strip packing problem, the items are not allowed to be rotated. However, variants have been studied where rotating by 90 degrees or even an arbitrary angle is allowed.

Structure:

In the general strip packing problem, the structure of the packing is irrelevant.

However, there are applications that have explicit requirements on the structure of the packing. One of these requirements is to be able to cut the items from the strip by horizontal or vertical edge-to-edge cuts.

Packings that allow this kind of cutting are called guillotine packing.

The strip packing problem contains the bin packing problem as a special case when all the items have the same height 1.

For this reason, it is strongly NP-hard, and there can be no polynomial time approximation algorithm that has an approximation ratio smaller than $3/2$ unless $P\; =\; NP$.

Furthermore, unless $P\; =\; NP$, there cannot be a pseudo-polynomial time algorithm that has an approximation ratio smaller than $5/4$,{{cite journal |last1=Henning |first1=Sören |last2=Jansen |first2=Klaus |last3=Rau |first3=Malin |last4=Schmarje |first4=Lars |title=Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing |journal=Theory of Computing Systems |volume=64 |pages=120–140 |date=2019 |doi=10.1007/s00224-019-09910-6|arxiv=1705.04587 |s2cid=67168004 }} which can be proven by a reduction from the strongly NP-complete 3-partition problem.

Note that both lower bounds $3/2$ and $5/4$ also hold for the case that a rotation of the items by 90 degrees is allowed.

Additionally, it was proven by Ashok et al.{{cite journal |last1=Ashok |first1=Pradeesha |last2=Kolay |first2=Sudeshna |last3=Meesum |first3=S.M. |last4=Saurabh |first4=Saket |title=Parameterized complexity of Strip Packing and Minimum Volume Packing |journal=Theoretical Computer Science |date=January 2017 |volume=661 |pages=56–64 |doi=10.1016/j.tcs.2016.11.034|doi-access=free }} that strip packing is W[1]-hard when parameterized by the height of the optimal packing.

There are two trivial lower bounds on optimal solutions.

The first is the height of the largest item.

Define $h\_\{\backslash max\}(I)\; :=\; \backslash max\backslash \{h(i)\; |\; i\; \backslash in\; \backslash mathcal\{I\}\backslash \}$.

Then it holds that

$OPT(I)\; \backslash geq\; h\_\{\backslash max\}(I)$.

Another lower bound is given by the total area of the items.

Define $\backslash mathrm\{AREA\}(\backslash mathcal\{I\})\; :=\; \backslash sum\_\{i\; \backslash in\; \backslash mathcal\{I\}\}h(i)w(i)$ then it holds that

$OPT(I)\; \backslash geq\; \backslash mathrm\{AREA\}(\backslash mathcal\{I\})/W$.

The following two lower bounds take notice of the fact that certain items cannot be placed next to each other in the strip, and can be computed in $\backslash mathcal\{O\}(n\; \backslash log(n))$.{{cite journal |last1=Martello |first1=Silvano |last2=Monaci |first2=Michele |last3=Vigo |first3=Daniele |title=An Exact Approach to the Strip-Packing Problem |journal=INFORMS Journal on Computing |date=1 August 2003 |volume=15 |issue=3 |pages=310–319 |doi=10.1287/ijoc.15.3.310.16082 |issn=1091-9856}}

For the first lower bound assume that the items are sorted by non-increasing height. Define $k\; :=\; \backslash max\; \backslash \{i\; :\; \backslash sum\_\{j\; =\; 1\}^k\; w(j)\; \backslash leq\; W\backslash \}$. For each $l\; >\; k$ define $i(l)\; \backslash leq\; k$ the first index such that $w(l)\; +\; \backslash sum\_\{j\; =\; 1\}^\{i(l)\}\; w(j)\; >\; W$. Then it holds that

$OPT(I)\; \backslash geq\; \backslash max\; \backslash \{h(l)\; +\; h(i(l))|\; l\; >k\; \backslash wedge\; w(l)\; +\; \backslash sum\_\{j\; =\; 1\}^\{i(l)\}\; w(j)\; >\; W\backslash \}$.

For the second lower bound, partition the set of items into three sets. Let $\backslash alpha\; \backslash in\; [1,\; W/2]\backslash cap\; \backslash mathbb\{N\}$ and define $\backslash mathcal\{I\}\_1(\backslash alpha)\; :=\; \backslash \{i\; \backslash in\; \backslash mathcal\{I\}\; |\; w(i)\; >\; W\; -\; \backslash alpha\backslash \}$, $\backslash mathcal\{I\}\_2(\backslash alpha)\; :=\; \backslash \{i\; \backslash in\; \backslash mathcal\{I\}\; |\; W\; -\; \backslash alpha\; \backslash geq\; w(i)\; >\; W/2\backslash \}$, and $\backslash mathcal\{I\}\_3(\backslash alpha)\; :=\; \backslash \{i\; \backslash in\; \backslash mathcal\{I\}\; |\; W/2\; \backslash geq\; w(i)\; >\; \backslash alpha\; \backslash \}$. Then it holds that

$$

OPT(I) \geq

\max_{\alpha \in [1, W/2]\cap \mathbb{N}}

\Bigg\{ \sum_{i \in \mathcal{I}_1(\alpha) \cup \mathcal{I}_2(\alpha)} h(i) + \left(\frac{\sum_{i \in \mathcal{I}_3(\alpha) h(i)w(i) - \sum_{i \in \mathcal{I}_2(\alpha)}(W -w(i))h(i)}}{W}\right)_+

\Bigg\}, where $(x)\_+\; :=\; \backslash max\backslash \{x,0\backslash \}$ for each $x\; \backslash in\; \backslash mathbb\{R\}$.

On the other hand, Steinberg has shown that the height of an optimal solution can be upper bounded by

$OPT(I)\; \backslash leq\; 2\backslash max\backslash \{h\_\{\backslash max\}(I),\backslash mathrm\{AREA\}(\backslash mathcal\{I\})/W\backslash \}.$

More precisely he showed that given a $W\; \backslash geq\; w\_\{\backslash max\}(\backslash mathcal\{I\})$ and a $H\; \backslash geq\; h\_\{\backslash max\}(I)$ then the items $\backslash mathcal\{I\}$ can be placed inside a box with width $W$ and height $H$ if

$WH\; \backslash geq\; 2\backslash mathrm\{AREA\}(\backslash mathcal\{I\})\; +\; (2w\_\{\backslash max\}(\backslash mathcal\{I\})\; -\; W)\_+(2h\_\{\backslash max\}(I)\; -\; H)\_+$, where $(x)\_+\; :=\; \backslash max\backslash \{x,0\backslash \}$.

Since this problem is NP-hard, approximation algorithms have been studied for this problem.

Most of the heuristic approaches have an approximation ratio between $3$ and $2$.

Finding an algorithm with a ratio below $2$ seems complicated, and

the complexity of the corresponding algorithms increases regarding their running time and their descriptions.

The smallest approximation ratio achieved so far is $(5/3+\backslash varepsilon)$.

class="wikitable" |+Overview of polynomial time approximations
Year	Name	Approximation guarantee	Source
1980	Bottom-Up Left-Justified (BL)	$3\; OPT(I)$	Baker et al.
rowspan="3"| 1980 |Next-Fit Decreasing-Height (NFDH) |$2\; OPT(I)\; +\; h\_\{\backslash max\}(I)\; \backslash leq\; 3\; OPT(I)$ |rowspan="3"|Coffman et al.{{cite journal |last1=Coffman Jr. |first1=Edward G. |last2=Garey |first2=M. R. |last3=Johnson |first3=David S. |last4=Tarjan |first4=Robert Endre |title=Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms |journal=SIAM J. Comput. |date=1980 |volume=9 |issue=4 |pages=808–826 |doi=10.1137/0209062}}
First-Fit Decreasing-Height (FFDH) |$1.7\; OPT(I)\; +\; h\_\{\backslash max\}(I)\; \backslash leq\; 2.7\; OPT(I)$
Split-Fit (SF) |$1.5\; OPT(I)\; +\; 2h\_\{\backslash max\}(I)$
1980		$2\; OPT(I)\; +\; h\_\{\backslash max\}(I)/2\; \backslash leq\; 2.5\; OPT(I)$	Sleator{{cite journal |last1=Sleator |first1=Daniel Dominic |title=A 2.5 Times Optimal Algorithm for Packing in Two Dimensions |journal=Inf. Process. Lett. |date=1980 |volume=10 |pages=37–40 |doi=10.1016/0020-0190(80)90121-0}}
rowspan="2"| 1981 | Split Algorithm (SP) |$3\; OPT(I)$ |rowspan="2"| Golan{{cite journal |last1=Golan |first1=Igal |title=Performance Bounds for Orthogonal Oriented Two-Dimensional Packing Algorithms |journal=SIAM Journal on Computing |date=August 1981 |volume=10 |issue=3 |pages=571–582 |doi=10.1137/0210042}}
Mixed Algoritghm | $(4/3)OPT(I)\; +\; 7\backslash frac\{1\}\{18\}\; h\_\{\backslash max\}(I)$
1981	Up-Down (UD)	$(5/4)OPT(I)\; +\; 6\backslash frac\{7\}\{8\}h\_\{\backslash max\}(I)$	Baker et al.{{cite journal |last1=Baker |first1=Brenda S |last2=Brown |first2=Donna J |last3=Katseff |first3=Howard P |title=A 5/4 algorithm for two-dimensional packing |journal=Journal of Algorithms |date=December 1981 |volume=2 |issue=4 |pages=348–368 |doi=10.1016/0196-6774(81)90034-1}}
1994	Reverse-Fit	$2\; OPT(I)$	Schiermeyer{{cite book |doi=10.1007/bfb0049416 |publisher=Springer Berlin Heidelberg |language=en|series=Lecture Notes in Computer Science |isbn=978-3-540-58434-6 |chapter=Reverse-Fit: A 2-optimal algorithm for packing rectangles |title=Algorithms — ESA '94 |volume=855 |pages=290–299 |year=1994 |last1=Schiermeyer |first1=Ingo }}
1997		$2\; OPT(I)$	Steinberg{{cite journal |last1=Steinberg |first1=A. |title=A Strip-Packing Algorithm with Absolute Performance Bound 2 |journal=SIAM Journal on Computing |date=March 1997 |volume=26 |issue=2 |pages=401–409 |doi=10.1137/S0097539793255801}}
2000 | |$(1+\backslash varepsilon)\; OPT(I)\; +\; \backslash mathcal\{O\}(1/\backslash varepsilon^2)h\_\{\backslash max\}(I)$ | Kenyon, Rémila{{cite journal | last1=Kenyon | first1=Claire | authorlink1=Claire Mathieu | last2=Rémila | first2=Eric | title=A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem | journal=Mathematics of Operations Research | date=November 2000 | volume=25 | issue=4 | pages=645–656 | doi=10.1287/moor.25.4.645.12118 | s2cid=5361969}}
2009 | |$1.9396\; OPT(I)$ | Harren, van Stee{{cite book |last1=Harren |first1=Rolf |last2=van Stee |first2=Rob |title=Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques |chapter=Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems |series=Lecture Notes in Computer Science |volume=5687 |date=2009 |pages=177–189 |doi=10.1007/978-3-642-03685-9_14 |bibcode=2009LNCS.5687..177H |isbn=978-3-642-03684-2 }}
2009		$(1+\backslash varepsilon)\; OPT(I)\; +\; h\_\{\backslash max\}(I)$	Jansen, Solis-Oba{{cite journal |last1=Jansen |first1=Klaus |last2=Solis-Oba |first2=Roberto |title=Rectangle packing with one-dimensional resource augmentation |journal=Discrete Optimization |date=August 2009 |volume=6 |issue=3 |pages=310–323 |doi=10.1016/j.disopt.2009.04.001}}
2011 | |$(1+\backslash varepsilon)\; OPT(I)\; +\; \backslash mathcal\{O\}(\backslash log(1/\backslash varepsilon)/\backslash varepsilon)h\_\{\backslash max\}(I)$ | Bougeret et al.{{cite journal |last1=Bougeret |first1=Marin |last2=Dutot|first2=Pierre-Francois|last3=Jansen|first3=Klaus |last4=Robenek|first4=Christina|last5=Trystram|first5=Denis |title=Approximation Algorithms for Multiple Strip Packing and Scheduking Parallel Jobs in Platforms|journal=Discrete Mathematics, Algorithms and Applications |date=5 April 2012 |volume=03 |issue=4 |pages=553–586 |doi=10.1142/S1793830911001413}}
2012 | |$(1+\backslash varepsilon)\; OPT(I)\; +\; \backslash mathcal\{O\}(\backslash log(1/\backslash varepsilon)/\backslash varepsilon)h\_\{\backslash max\}(I)$ | Sviridenko{{cite journal |last1=Sviridenko |first1=Maxim |title=A note on the Kenyon–Remila strip-packing algorithm |journal=Information Processing Letters |date=January 2012 |volume=112 |issue=1–2 |pages=10–12 |doi=10.1016/j.ipl.2011.10.003}}
2014		$(5/3+\backslash varepsilon)\; OPT(I)$	Harren et al.{{cite journal |last1=Harren |first1=Rolf |last2=Jansen |first2=Klaus |last3=Prädel |first3=Lars |last4=van Stee |first4=Rob |title=A (5/3 + epsilon)-approximation for strip packing |journal=Computational Geometry |date=February 2014 |volume=47 |issue=2 |pages=248–267 |doi=10.1016/j.comgeo.2013.08.008|doi-access=free }}

File:BL Example2.pdf

This algorithm was first described by Baker et al. It works as follows:

Let $L$ be a sequence of rectangular items.

The algorithm iterates the sequence in the given order.

For each considered item $r\; \backslash in\; L$, it searches for the bottom-most position to place it and then shifts it as far to the left as possible.

Hence, it places $r$ at the bottom-most left-most possible coordinate $(x,y)$ in the strip.

This algorithm has the following properties:

• The approximation ratio of this algorithm cannot be bounded by a constant. More precisely they showed that for each $M\; >\; 0$ there exists a list $L$ of rectangular items ordered by increasing width such that $BL(L)/\; OPT(L)\; >\; M$, where $BL(L)$ is the height of the packing created by the BL algorithm and $OPT(L)$ is the height of the optimal solution for $L$.
• If the items are ordered by decreasing widths, then $BL(L)/\; OPT(L)\; \backslash leq\; 3$.
• If the item are all squares and are ordered by decreasing widths, then $BL(L)/\; OPT(L)\; \backslash leq\; 2$.
• For any $\backslash delta\; >\; 0$, there exists a list $L$ of rectangles ordered by decreasing widths such that $BL(L)/\; OPT(L)\; >\; 3\; -\; \backslash delta$.
• For any $\backslash delta\; >\; 0$, there exists a list $L$ of squares ordered by decreasing widths such that $BL(L)/\; OPT(L)\; >\; 2\; -\; \backslash delta$.
• For each $\backslash varepsilon\; \backslash in\; (0,1]$, there exists an instance containing only squares where each order of the squares $L$ has a ratio of $BL(L)/\; OPT(L)\; >\; \backslash frac\{12\}\{11\; +\backslash varepsilon\}$, i.e., there exist instances where BL does not find the optimum even when iterating all possible orders of the items. In 2024 this lower bound has been improved by Hougardy and Zondervan to $BL(L)/\; OPT(L)\; >\; \backslash frac\{4\}\{3\; +\backslash varepsilon\}$.{{Citation |last1=Hougardy |first1=Stefan |title=The Bottom-Left Algorithm for the Strip Packing Problem |date=2024-02-26 |arxiv=2402.16572 |last2=Zondervan |first2=Bart}}

File:ExampleNFDHvsFFDH.png

This algorithm was first described by Coffman et al. in 1980 and works as follows:

Let $\backslash mathcal\{I\}$ be the given set of rectangular items.

First, the algorithm sorts the items by order of nonincreasing height.

Then, starting at position $(0,0)$, the algorithm places the items next to each other in the strip until the next item will overlap the right border of the strip.

At this point, the algorithm defines a new level at the top of the tallest item in the current level and places the items next to each other in this new level.

This algorithm has the following properties:

• The running time can be bounded by $\backslash mathcal\{O\}(|\backslash mathcal\{I\}|\; \backslash log(|\backslash mathcal\{I\}|))$ and if the items are already sorted even by $\backslash mathcal\{O\}(|\backslash mathcal\{I\}|)$.
• For every set of items $\backslash mathcal\{I\}$, it produces a packing of height $NFDH(\backslash mathcal\{I\})\; \backslash leq\; 2\; OPT(\backslash mathcal\{I\})\; +\; h\_\{\backslash max\}\; \backslash leq\; 3\; OPT(\backslash mathcal\{I\})$, where $h\_\{\backslash max\}$ is the largest height of an item in $\backslash mathcal\{I\}$.
• For every $\backslash varepsilon\; >\; 0$ there exists a set of rectangles $\backslash mathcal\{I\}$ such that $NFDH(\backslash mathcal\{I\}|)\; >\; (2-\backslash varepsilon)\; OPT(\backslash mathcal\{I\}).$
• The packing generated is a guillotine packing. This means the items can be obtained through a sequence of horizontal or vertical edge-to-edge cuts.

This algorithm, first described by Coffman et al. in 1980, works similar to the NFDH algorithm.

However, when placing the next item, the algorithm scans the levels from bottom to top and places the item in the first level on which it will fit.

A new level is only opened if the item does not fit in any previous ones.

This algorithm has the following properties:

• The running time can be bounded by $\backslash mathcal\{O\}(|\backslash mathcal\{I\}|^2)$, since there are at most $|\backslash mathcal\{I\}|$ levels.
• For every set of items $\backslash mathcal\{I\}$ it produces a packing of height $FFDH(\backslash mathcal\{I\})\; \backslash leq\; 1.7\; OPT(\backslash mathcal\{I\})\; +\; h\_\{\backslash max\}\; \backslash leq\; 2.7\; OPT(\backslash mathcal\{I\})$, where $h\_\{\backslash max\}$ is the largest height of an item in $\backslash mathcal\{I\}$.
• Let $m\; \backslash geq\; 2$. For any set of items $\backslash mathcal\{I\}$ and strip with width $W$ such that $w(i)\; \backslash leq\; W/m$ for each $i\; \backslash in\; \backslash mathcal\{I\}$, it holds that $FFDH(\backslash mathcal\{I\})\; \backslash leq\; \backslash left(1\; +\; 1/m\backslash right)\; OPT(\backslash mathcal\{I\})\; +\; h\_\{\backslash max\}$. Furthermore, for each $\backslash varepsilon\; >\; 0$, there exists such a set of items $\backslash mathcal\{I\}$ with $FFDH(\backslash mathcal\{I\})\; >\; \backslash left(1\; +\; 1/m\; -\backslash varepsilon\backslash right)OPT(\backslash mathcal\{I\})$.
• If all the items in $\backslash mathcal\{I\}$ are squares, it holds that $FFDH(\backslash mathcal\{I\})\; \backslash leq\; (3/2)\; OPT(\backslash mathcal\{I\})\; +\; h\_\{\backslash max\}$. Furthermore, for each $\backslash varepsilon\; >0$, there exists a set of squares $\backslash mathcal\{I\}$ such that $FFDH(\backslash mathcal\{I\})\; >\; \backslash left(3/2-\backslash varepsilon\backslash right)OPT(\backslash mathcal\{I\})$.
• The packing generated is a guillotine packing. This means the items can be obtained through a sequence of horizontal or vertical edge-to-edge cuts.

This algorithm was first described by Coffman et al.

For a given set of items $\backslash mathcal\{I\}$ and strip with width $W$, it works as follows:

1. Determinate $m\; \backslash in\; \backslash mathbb\{N\}$, the largest integer such that the given rectangles have width $W/m$ or less.
2. Divide $\backslash mathcal\{I\}$ into two sets $\backslash mathcal\{I\}\_\{wide\}$ and $\backslash mathcal\{I\}\_\{narrow\}$, such that $\backslash mathcal\{I\}\_\{wide\}$ contains all the items $i\; \backslash in\; \backslash mathcal\{I\}$ with a width $w(i)\; >\; W/(m+1)$ while $\backslash mathcal\{I\}\_\{narrow\}$ contains all the items with $w(i)\; \backslash leq\; W/(m+1)$.
3. Order $\backslash mathcal\{I\}\_\{wide\}$ and $\backslash mathcal\{I\}\_\{narrow\}$ by nonincreasing height.
4. Pack the items in $\backslash mathcal\{I\}\_\{wide\}$ with the FFDH algorithm.
5. Reorder the levels/shelves constructed by FFDH such that all the shelves with a total width larger than $W(m+1)/(m+2)$ are below the more narrow ones.
6. This leaves a rectangular area $R$ of with $W/(m+2)$, next to more narrow levels/shelves, that contains no item.
7. Use the FFDH algorithm to pack the items in $\backslash mathcal\{I\}\_\{narrow\}$ using the area $R$ as well.

This algorithm has the following properties:

• For every set of items $\backslash mathcal\{I\}$ and the corresponding $m$, it holds that $SF(\backslash mathcal\{I\})\; \backslash leq\; (m+2)/(m+1)OPT(\backslash mathcal\{I\})\; +\; 2h\_\{\backslash max\}$. Note that for $m=1$, it holds that $SF(\backslash mathcal\{I\})\; \backslash leq\; (3/2)\; OPT(\backslash mathcal\{I\})\; +\; 2h\_\{\backslash max\}$
• For each $\backslash varepsilon\; >0$, there is a set of items $\backslash mathcal\{I\}$ such that $SF(\backslash mathcal\{I\})\; >\; \backslash left((m+2)/(m+1)\; -\backslash varepsilon\backslash right)OPT(\backslash mathcal\{I\})$.

For a given set of items $\backslash mathcal\{I\}$ and strip with width $W$, it works as follows:

1. Find all the items with a width larger than $W/2$ and stack them at the bottom of the strip (in random order). Call the total height of these items $h\_0$. All the other items will be placed above $h\_0$.
2. Sort all the remaining items in nonincreasing order of height. The items will be placed in this order.
3. Consider the horizontal line at $h\_0$ as a shelf. The algorithm places the items on this shelf in nonincreasing order of height until no item is left or the next one does not fit.
4. Draw a vertical line at $W/2$, which cuts the strip into two equal halves.
5. Let $h\_l$ be the highest point covered by any item in the left half and $h\_r$ the corresponding point on the right half. Draw two horizontal line segments of length $W/2$ at $h\_l$ and $h\_r$ across the left and the right half of the strip. These two lines build new shelves on which the algorithm will place the items, as in step 3. Choose the half which has the lower shelf and place the items on this shelf until no other item fits. Repeat this step until no item is left.

This algorithm has the following properties:

• The running time can be bounded by $\backslash mathcal\{O\}(|\backslash mathcal\{I\}|\; \backslash log(|\backslash mathcal\{I\}|))$ and if the items are already sorted even by $\backslash mathcal\{O\}(|\backslash mathcal\{I\}|)$.
• For every set of items $\backslash mathcal\{I\}$ it produces a packing of height $A(\backslash mathcal\{I\})\; \backslash leq\; 2\; OPT(\backslash mathcal\{I\})\; +\; h\_\{\backslash max\}/2\; \backslash leq\; 2.5\; OPT(\backslash mathcal\{I\})$, where $h\_\{\backslash max\}$ is the largest height of an item in $\backslash mathcal\{I\}$.

This algorithm is an extension of Sleator's approach and was first described by Golan.

It places the items in nonincreasing order of width.

The intuitive idea is to split the strip into sub-strips while placing some items.

Whenever possible, the algorithm places the current item $i$ side-by-side of an already placed item $j$.

In this case, it splits the corresponding sub-strip into two pieces: one containing the first item $j$ and the other containing the current item $i$.

If this is not possible, it places $i$ on top of an already placed item and does not split the sub-strip.

This algorithm creates a set S of sub-strips. For each sub-strip s ∈ S we know its lower left corner s.xposition and s.yposition, its width s.width, the horizontal lines parallel to the upper and lower border of the item placed last inside this sub-strip s.upper and s.lower, as well as the width of it s.itemWidth.

function Split Algorithm (SP) is

input: items I, width of the strip W

output: A packing of the items

Sort I in nonincreasing order of widths;

Define empty list S of sub-strips;

Define a new sub-strip s with s.xposition = 0, s.yposition = 0, s.width = W, s.lower = 0, s.upper = 0, s.itemWidth = W;

Add s to S;

while I not empty do

i := I.pop(); Removes widest item from I

Define new list S_2 containing all the substrips with s.width - s.itemWidth ≥ i.width;

S_2 contains all sub-strips where i fits next to the already placed item

if S_2 is empty then

In this case, place the item on top of another one.

Find the sub-strip s in S with smallest s.upper; i.e. the least filled sub-strip

Place i at position (s.xposition, s.upper);

Update s: s.lower := s.upper; s.upper := s.upper+i.height; s.itemWidth := i.width;

else

In this case, place the item next to another one at the same level and split the corresponding sub-strip at this position.

Find s ∈ S_2 with the smallest s.lower;

Place i at position (s.xposition + s.itemWidth, s.lower);

Remove s from S;

Define two new sub-strips s1 and s2 with

s1.xposition = s.xposition, s1.yposition = s.upper, s1.width = s.itemWidth, s1.lower = s.upper, s1.upper = s.upper, s1.itemWidth = s.itemWidth;

s2.xposition = s.xposition+s.itemWidth, s2.yposition = s.lower, s2.width = s.width - s.itemWidth, s2.lower = s.lower, s2.upper = s.lower + i.height, s2.itemWidth = i.width;

S.add(s1,s2);

return

end function

This algorithm has the following properties:

• The running time can be bounded by $\backslash mathcal\{O\}(|\backslash mathcal\{I\}|^2)$ since the number of substrips is bounded by $|\backslash mathcal\{I\}|$.
• For any set of items $\backslash mathcal\{I\}$ it holds that $SP(\backslash mathcal\{I\})\; \backslash leq\; 2\; OPT(\backslash mathcal\{I\})\; +\; h\_\{\backslash max\}\; \backslash leq\; 3\; OPT(\backslash mathcal\{I\})$.
• For any $\backslash varepsilon\; >0$, there exists a set of items $\backslash mathcal\{I\}$ such that $SP(\backslash mathcal\{I\})\; >\; (3-\backslash varepsilon)\; OPT(\backslash mathcal\{I\})$.
• For any $\backslash varepsilon\; >0$ and $C>0$, there exists a set of items $\backslash mathcal\{I\}$ such that $SP(\backslash mathcal\{I\})\; >\; (2-\backslash varepsilon)\; OPT(\backslash mathcal\{I\})+C$.

This algorithm was first described by Schiermeyer.

The description of this algorithm needs some additional notation.

For a placed item $i\; \backslash in\; \backslash mathcal\{I\}$, its lower left corner is denoted by $(a\_i,c\_i)$ and its upper right corner by $(b\_i,d\_i)$.

Given a set of items $\backslash mathcal\{I\}$ and a strip of width $W$, it works as follows:

1. Stack all the rectangles of width greater than $W/2$ on top of each other (in random order) at the bottom of the strip. Denote by $H\_0$ the height of this stack. All other items will be packed above $H\_0$.
2. Sort the remaining items in order of nonincreasing height and consider the items in this order in the following steps. Let $h\_\{\backslash max\}$ be the height of the tallest of these remaining items.
3. Place the items one by one left aligned on a shelf defined by $H\_0$ until no other item fit on this shelf or there is no item left. Call this shelf the first level.
4. Let $h\_1$ be the height of the tallest unpacked item. Define a new shelf at $H\_0\; +\; h\_\{\backslash max\}\; +\; h\_1$. The algorithm will fill this shelf from right to left, aligning the items to the right, such that the items touch this shelf with their top. Call this shelf the second reverse-level.
5. Place the items into the two shelves due to First-Fit, i.e., placing the items in the first level where they fit and in the second one otherwise. Proceed until there are no items left, or the total width of the items in the second shelf is at least $W/2$.
6. Shift the second reverse-level down until an item from it touches an item from the first level. Define $H\_1$ as the new vertical position of the shifted shelf. Let $f$ and $s$ be the right most pair of touching items with $f$ placed on the first level and $s$ on the second reverse-level. Define $x\_r\; :=\; \backslash max(b\_f,b\_s)$.
7. If then $s$ is the last rectangle placed in the second reverse-level. Shift all the other items from this level further down (all the same amount) until the first one touches an item from the first level. Again the algorithm determines the rightmost pair of touching items $f\text{'}$ and $s\text{'}$. Define $h\_2$ as the amount by which the shelf was shifted down.
8. If $h\_2\; \backslash leq\; h(s)$ then shift $s$ to the left until it touches another item or the border of the strip. Define the third level at the top of $s\text{'}$.
9. If $h\_2\; >\; h(s)$ then shift $s$ define the third level at the top of $s\text{'}$. Place $s$ left-aligned in this third level, such that it touches an item from the first level on its left.
10. Continue packing the items using the First-Fit heuristic. Each following level (starting at level three) is defined by a horizontal line through the top of the largest item on the previous level. Note that the first item placed in the next level might not touch the border of the strip with their left side, but an item from the first level or the item $s$.

This algorithm has the following properties:

• The running time can be bounded by $\backslash mathcal\{O\}(|\backslash mathcal\{I\}|^2)$, since there are at most $|\backslash mathcal\{I\}|$ levels.
• For every set of items $\backslash mathcal\{I\}$ it produces a packing of height $RF(\backslash mathcal\{I\})\; \backslash leq\; 2\; OPT(\backslash mathcal\{I\})$.

Steinbergs algorithm is a recursive one. Given a set of rectangular items $\backslash mathcal\{I\}$ and a rectangular target region with width $W$ and height $H$, it proposes four reduction rules, that place some of the items and leaves a smaller rectangular region with the same properties as before regarding of the residual items.

Consider the following notations: Given a set of items $\backslash mathcal\{I\}$ we denote by $h\_\{\backslash max\}(\backslash mathcal\{I\})$ the tallest item height in $\backslash mathcal\{I\}$, $w\_\{\backslash max\}(\backslash mathcal\{I\})$ the largest item width appearing in $\backslash mathcal\{I\}$ and by $\backslash mathrm\{AREA\}(\backslash mathcal\{I\})\; :=\; \backslash sum\_\{i\; \backslash in\; \backslash mathcal\{I\}\}\; w(i)h(i)$ the total area of these items.

Steinbergs shows that if

$h\_\{\backslash max\}(\backslash mathcal\{I\})\; \backslash leq\; H$, $w\_\{\backslash max\}(\backslash mathcal\{I\})\; \backslash leq\; W$, and $\backslash mathrm\{AREA\}(\backslash mathcal\{I\})\; \backslash leq\; W\backslash cdot\; H\; -\; (2h\_\{\backslash max\}(\backslash mathcal\{I\})\; -h)\_+(2w\_\{\backslash max\}(\backslash mathcal\{I\})\; -\; W)\_+$, where $(a)\_+\; :=\; \backslash max\backslash \{0,a\backslash \}$,

then all the items can be placed inside the target region of size $W\; \backslash times\; H$.

Each reduction rule will produce a smaller target area and a subset of items that have to be placed. When the condition from above holds before the procedure started, then the created subproblem will have this property as well.

Procedure 1: It can be applied if $w\_\{\backslash max\}(\backslash mathcal\{I\}\text{'})\; \backslash geq\; W/2$.

1. Find all the items $i\; \backslash in\; \backslash mathcal\{I\}$ with width $w(i)\; \backslash geq\; W/2$ and remove them from $\backslash mathcal\{I\}$.
2. Sort them by nonincreasing width and place them left-aligned at the bottom of the target region. Let $h\_0$ be their total height.
3. Find all the items $i\; \backslash in\; \backslash mathcal\{I\}$ with width $h(i)\; >\; H-h\_0$. Remove them from $\backslash mathcal\{I\}$ and place them in a new set $\backslash mathcal\{I\}\_H$.
4. If $\backslash mathcal\{I\}\_H$ is empty, define the new target region as the area above $h\_0$, i.e. it has height $H-h\_0$ and width $W$. Solve the problem consisting of this new target region and the reduced set of items with one of the procedures.
5. If $\backslash mathcal\{I\}\_H$ is not empty, sort it by nonincreasing height and place the items right allinged one by one in the upper right corner of the target area. Let $w\_0$ be the total width of these items. Define a new target area with width $W-w\_0$ and height $H\; -\; h\_0$ in the upper left corner. Solve the problem consisting of this new target region and the reduced set of items with one of the procedures.

Procedure 2: It can be applied if the following conditions hold: $w\_\{\backslash max\}(\backslash mathcal\{I\})\; \backslash leq\; W/2$, $h\_\{\backslash max\}(\backslash mathcal\{I\})\; \backslash leq\; H/2$, and there exist two different items $i,i\text{'}\; \backslash in\; \backslash mathcal\{I\}$ with $w(i)\; \backslash geq\; W/4$, $w(i\text{'})\; \backslash geq\; W/4$, $h(i)\; \backslash geq\; H/4$, $h(i\text{'})\; \backslash geq\; H/4$ and $2(\backslash mathrm\{AREA\}(\backslash mathcal\{I\})\; -\; w(i)h(i)\; -w(i\text{'})h(i\text{'}))\; \backslash leq\; (W-\; \backslash max\backslash \{w(i),w(i\text{'})\backslash \})H$.

1. Find $i$ and $i\text{'}$ and remove them from $\backslash mathcal\{I\}$.
2. Place the wider one in the lower-left corner of the target area and the more narrow one left-aligned on the top of the first.
3. Define a new target area on the right of these both items, such that it has the width $W-\; \backslash max\backslash \{w(i),w(i\text{'})\backslash \}$ and height $H$.
4. Place the residual items in $\backslash mathcal\{I\}$ into the new target area using one of the procedures.

Procedure 3: It can be applied if the following conditions hold: $w\_\{\backslash max\}(\backslash mathcal\{I\})\; \backslash leq\; W/2$, $h\_\{\backslash max\}(\backslash mathcal\{I\})\; \backslash leq\; H/2$, $|\backslash mathcal\{I\}|\; >\; 1$, and when sorting the items by decreasing width there exist an index $m$ such that when defining $\backslash mathcal\{I\text{'}\}$ as the first $m$ items it holds that

$\backslash mathrm\{AREA\}(\backslash mathcal\{I\})-\; WH/4\; \backslash leq\; \backslash mathrm\{AREA\}(\backslash mathcal\{I\text{'}\})\; \backslash leq\; 3WH/8$ as well as $w(i\_\{m+1\})\backslash leq\; W/4$

1. Set $W\_1\; :=\; \backslash max\{W/2,\; 2\backslash mathrm\{AREA\}(\backslash mathcal\{I\text{'}\})/H\}$.
2. Define two new rectangular target areas one at the lower-left corner of the original one with height $H$ and width $W\_1$ and the other left of it with height $H$ and width $W-W\_1$.
3. Use one of the procedures to place the items in $\backslash mathcal\{I\text{'}\}$ into the first new target area and the items in $\backslash mathcal\{I\}\backslash setminus\backslash mathcal\{I\text{'}\}$ into the second one.

Note that procedures 1 to 3 have a symmetric version when swapping the height and the width of the items and the target region.

Procedure 4: It can be applied if the following conditions hold: $w\_\{\backslash max\}(\backslash mathcal\{I\})\; \backslash leq\; W/2$, $h\_\{\backslash max\}(\backslash mathcal\{I\})\; \backslash leq\; H/2$, and there exists an item $i\; \backslash in\; \backslash mathcal\{I\}$ such that $w(i)\; h(i)\; \backslash geq\; \backslash mathrm\{AREA\}(\backslash mathcal\{I\})\; -\; WH/4$.

1. Place the item $i$ in the lower-left corner of the target area and remove it from $\backslash mathcal\{I\}$.
2. Define a new target area right of this item such that it has the width $W-w(i)$ and height $H$ and place the residual items inside this area using one of the procedures.

This algorithm has the following properties:

• The running time can be bounded by $\backslash mathcal\{O\}(|\backslash mathcal\{I\}|\; \backslash log(|\backslash mathcal\{I\}|)^2/\backslash log(\backslash log(|\backslash mathcal\{I\}|)))$.
• For every set of items $\backslash mathcal\{I\}$ it produces a packing of height $ST(\backslash mathcal\{I\})\; \backslash leq\; 2\; OPT(\backslash mathcal\{I\})$.

To improve upon the lower bound of $3/2$ for polynomial-time algorithms, pseudo-polynomial time algorithms for the strip packing problem have been considered.

When considering this type of algorithms, all the sizes of the items and the strip are given as integrals. Furthermore, the width of the strip $W$ is allowed to appear polynomially in the running time.

Note that this is no longer considered as a polynomial running time since, in the given instance, the width of the strip needs an encoding size of $\backslash log(W)$.

The pseudo-polynomial time algorithms that have been developed mostly use the same approach. It is shown that each optimal solution can be simplified and transformed into one that has one of a constant number of structures. The algorithm then iterates all these structures and places the items inside using linear and dynamic programming. The best ratio accomplished so far is $(5/4\; +\backslash varepsilon)\; OPT(I)$. while there cannot be a pseudo-polynomial time algorithm with ratio better than $5/4$ unless $P\; =\; NP$

class="wikitable" |+Overview of pseudo-polynomial time approximations
Year	Approximation Ratio	Source	Comment
2010 | $(3/2\; +\backslash varepsilon)$ | Jansen, Thöle{{cite journal |last1=Jansen |first1=Klaus |last2=Thöle |first2=Ralf |title=Approximation Algorithms for Scheduling Parallel Jobs |journal=SIAM Journal on Computing |date=January 2010 |volume=39 |issue=8 |pages=3571–3615 |doi=10.1137/080736491}}
2016 | $(7/5\; +\backslash varepsilon)$ |Nadiradze, Wiese{{cite book |last1=Nadiradze |first1=Giorgi |last2=Wiese |first2=Andreas |title=Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms |chapter=On approximating strip packing with a better ratio than 3/2 |date=21 December 2015 |pages=1491–1510 |doi=10.1137/1.9781611974331.ch102 |publisher=Society for Industrial and Applied Mathematics|isbn=978-1-61197-433-1 }}
2016 | $(4/3\; +\backslash varepsilon)$ |Gálvez, Grandoni, Ingala, Khan{{cite book |last1=Gálvez |first1=Waldo |last2=Grandoni |first2=Fabrizio |last3=Ingala |first3=Salvatore |last4=Khan |first4=Arindam |title=Improved Pseudo-Polynomial-Time Approximation for Strip Packing |series=Leibniz International Proceedings in Informatics (LIPIcs) |date=2016 |volume=65 |pages=9:1–9:14 |doi=10.4230/LIPIcs.FSTTCS.2016.9 |publisher=Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik|doi-access=free |isbn=9783959770279 |s2cid=3205478 }} | also for 90 degree rotations
2017 |$(4/3\; +\backslash varepsilon)$ |Jansen, Rau{{cite book |last1=Jansen |first1=Klaus |last2=Rau |first2=Malin |title=WALCOM: Algorithms and Computation |chapter=Improved Approximation for Two Dimensional Strip Packing with Polynomial Bounded Width |series=Lecture Notes in Computer Science |date=29–31 March 2017 |volume=10167 |pages=409–420 |doi=10.1007/978-3-319-53925-6_32 |arxiv=1610.04430 |isbn=978-3-319-53924-9 |s2cid=15768136 }}
2019 |$(5/4\; +\backslash varepsilon)$ |Jansen, Rau{{cite book |last1=Jansen |first1=Klaus |last2=Rau |first2=Malin |title=Closing the Gap for Pseudo-Polynomial Strip Packing |series=Leibniz International Proceedings in Informatics (LIPIcs) |date=2019 |volume=144 |pages=62:1–62:14 |doi=10.4230/LIPIcs.ESA.2019.62 |publisher=Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik|doi-access=free |isbn=9783959771245 |s2cid=24303167 }} | also for 90 degree rotations and contiguous moldable jobs

In the online variant of strip packing, the items arrive over time. When an item arrives, it has to be placed immediately before the next item is known. There are two types of online algorithms that have been considered. In the first variant, it is not allowed to alter the packing once an item is placed. In the second, items may be repacked when another item arrives. This variant is called the migration model.

The quality of an online algorithm is measured by the (absolute) competitive ratio

$\backslash mathrm\{sup\}\_I\; A(I)/OPT(I)$,

where $A(I)$ corresponds to the solution generated by the online algorithm and $OPT(I)$ corresponds to the size of the optimal solution.

In addition to the absolute competitive ratio, the asymptotic competitive ratio of online algorithms has been studied. For instances $I$ with $h\_\{\backslash max\}(I)\backslash leq\; 1$ it is defined as

$\backslash lim\; \backslash mathrm\{sup\}\_\{OPT(I)\; \backslash rightarrow\; \backslash infty\}\; A(I)/OPT(I)$.

Note that all the instances can be scaled such that $h\_\{\backslash max\}(I)\backslash leq\; 1$.

class="wikitable" |+Overview of online algorithms without migration
Year	Competitive Ratio	Asymptotic Competitive Ratio	Source
1983 | 6.99 | $\backslash approx\; 1.7$ | Baker and Schwarz{{cite journal |last1=Baker |first1=Brenda S. |last2=Schwarz |first2=Jerald S. |title=Shelf Algorithms for Two-Dimensional Packing Problems |journal=SIAM Journal on Computing |date=1 August 1983 |volume=12 |issue=3 |pages=508–525 |doi=10.1137/0212033 |issn=0097-5397}}
1997 | | $1.69+\backslash varepsilon$ | Csirik and Woeginger{{cite journal |last1=Csirik |first1=János |last2=Woeginger |first2=Gerhard J. |title=Shelf algorithms for on-line strip packing |journal=Information Processing Letters |date=28 August 1997 |volume=63 |issue=4 |pages=171–175 |doi=10.1016/S0020-0190(97)00120-8 |issn=0020-0190}}
2007 |6.6623 | |Hurink and Paulus{{cite book |last1=Hurink |first1=Johann L. |last2=Paulus |first2=Jacob Jan |title=Approximation and Online Algorithms |chapter=Online Algorithm for Parallel Job Scheduling and Strip Packing |volume=4927 |date=2007 |pages=67–74 |doi=10.1007/978-3-540-77918-6_6 |publisher=Springer Berlin Heidelberg |language=en|series=Lecture Notes in Computer Science |isbn=978-3-540-77917-9 |chapter-url=https://ris.utwente.nl/ws/files/5327458/ParallelJobStripPacking.pdf }}
2009 |6.6623 | |Ye, Han, and Zhang{{cite journal |last1=Ye |first1=Deshi |last2=Han |first2=Xin |last3=Zhang |first3=Guochuan |title=A note on online strip packing |journal=Journal of Combinatorial Optimization |date=1 May 2009 |volume=17 |issue=4 |pages=417–423 |doi=10.1007/s10878-007-9125-x |s2cid=37635252 |language=en |issn=1573-2886}}
2007 | |$1.58889$ | Han et al.{{cite book |last1=Han |first1=Xin |last2=Iwama |first2=Kazuo |last3=Ye |first3=Deshi |last4=Zhang |first4=Guochuan |title=Algorithmic Aspects in Information and Management |chapter=Strip Packing vs. Bin Packing |volume=4508 |date=2007 |pages=358–367 |doi=10.1007/978-3-540-72870-2_34 |publisher=Springer Berlin Heidelberg |language=en|series=Lecture Notes in Computer Science |isbn=978-3-540-72868-9 |arxiv=cs/0607046 |s2cid=580 }} + Seiden{{cite book |last1=Seiden |first1=Steven S. |title=Automata, Languages and Programming |chapter=On the Online Bin Packing Problem |volume=2076 |date=2001 |pages=237–248 |doi=10.1007/3-540-48224-5_20 |publisher=Springer Berlin Heidelberg |language=en|series=Lecture Notes in Computer Science |isbn=978-3-540-42287-7 }}

The framework of Han et al. is applicable in the online setting if the online bin packing

algorithm belongs to the class Super Harmonic. Thus, Seiden's online bin packing algorithm

Harmonic++ implies an algorithm for online strip packing with asymptotic ratio 1.58889.

class="wikitable" |+Overview of lower bounds for online algorithms without migration
Year	Competitive Ratio	Asymptotic Competitive Ratio	Source	Comment
1982 |$2$ | | Brown, Baker, and Katseff{{cite journal |last1=Brown |first1=Donna J. |last2=Baker |first2=Brenda S. |last3=Katseff |first3=Howard P. |title=Lower bounds for on-line two-dimensional packing algorithms |journal=Acta Informatica |date=1 November 1982 |volume=18 |issue=2 |pages=207–225 |doi=10.1007/BF00264439 |language=en |issn=1432-0525|hdl=2142/74223 |s2cid=21170278 |hdl-access=free }}
2006 |2.25 | |Johannes{{cite journal |last1=Johannes |first1=Berit |title=Scheduling parallel jobs to minimize the makespan |journal=Journal of Scheduling |date=1 October 2006 |volume=9 |issue=5 |pages=433–452 |doi=10.1007/s10951-006-8497-6 |hdl=20.500.11850/36804 |s2cid=18819458 |language=en |issn=1099-1425|url=http://doc.rero.ch/record/318381/files/10951_2006_Article_8497.pdf }} | also holds for the parallel task scheduling problem
2007 |2.43 | | Hurink and Paulus{{cite journal |last1=Hurink |first1=J. L. |last2=Paulus |first2=J. J. |title=Online scheduling of parallel jobs on two machines is 2-competitive |journal=Operations Research Letters |date=1 January 2008 |volume=36 |issue=1 |pages=51–56 |doi=10.1016/j.orl.2007.06.001 |s2cid=15561044 |issn=0167-6377|url=https://ris.utwente.nl/ws/files/6547720/Online_scheduling_of_parallel_jobs_on_two_machines_is_2_competitive.pdf }} | also holds for the parallel task scheduling problem
2009 | 2.457 | | Kern and Paulus {{cite journal |last1=Kern |first1=Walter |last2=Paulus |first2=Jacob Jan |title=A note on the lower bound for online strip packing |journal=Operations Research Letters |date=2009|url=https://research.utwente.nl/en/publications/a-note-on-the-lower-bound-for-online-strip-packing}}
2012 | | $1.5404$ | Balogh and Békési{{cite journal |last1=Balogh |first1=János |last2=Békési |first2=József |last3=Galambos |first3=Gábor |title=New lower bounds for certain classes of bin packing algorithms |journal=Theoretical Computer Science |date=6 July 2012 |volume=440-441 |pages=1–13 |doi=10.1016/j.tcs.2012.04.017 |issn=0304-3975|doi-access=free }} | lower bound due to the underlying bin packing problem
2016 | 2.618 | | Yu, Mao, and Xiao{{cite journal |last1=Yu |first1=Guosong |last2=Mao |first2=Yanling |last3=Xiao |first3=Jiaoliao |title=A new lower bound for online strip packing |journal=European Journal of Operational Research |date=1 May 2016 |volume=250 |issue=3 |pages=754–759 |doi=10.1016/j.ejor.2015.10.012 |issn=0377-2217}}

{{reflist}}

Category:Mathematical analysis

Category:Packing problems

Category:Strongly NP-complete problems