Strip packing problem
The strip packing problem is a 2-dimensional geometric minimization problem. Given a set of axis-aligned rectangles and a strip of bounded width and infinite height, determine an overlapping-free packing of the rectangles into the strip minimizing its height. This problem is a cutting and packing problem and is classified as an "Open Dimension Problem" according to Wäscher et al. This problem arises in the area of scheduling, where it models jobs, that require a contiguous portion of the memory over a given time period. Another example is the area of industrial manufacturing, where rectangular  pieces need to be cut out of a sheet of material (e.g., cloth or paper) that has a fixed width but infinite length, and one wants to minimize the wasted material. This problem was first studied in 1980. It is strongly-NP hard and there exists no polynomial time approximation algorithm with a ratio smaller than formula_1 unless formula_2. However, the best approximation ratio achieved so far (by a polynomial time algorithm by Harren et al.) is formula_3, imposing an open question whether there is an algorithm with approximation ratio formula_1. Definition. An instance formula_5 of the strip packing problem  consists of a strip with width formula_6 and infinite height, as well as a set formula_7 of rectangular items. Each item formula_8 has a width formula_9 and a height formula_10. A packing of the items is a mapping that maps each lower-left corner of an item formula_8 to a position formula_12 inside the strip. An inner point of a placed item formula_8 is a point from the set formula_14. Two (placed) items overlap if they share an inner point. The height of the packing is defined as formula_15. 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. Variants. There are several variants of the strip packing problem that have been studied. These variants concern the geometry of the objects, dimension of the problem, if it is allowed to rotate  the items, and the structure of the packing. Geometry of the items: 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 have been studied where the shapes are circular or even irregular. In the latter case, we speak of "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, it is not allowed to rotate the items. However, variants have been studied where rotating by 90 degrees or even an arbitrary angle is allowed. Structure of the packing: 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. Hardness. 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, which has an approximation ratio smaller than formula_1 unless formula_2. Furthermore, unless formula_2, there cannot be a pseudo-polynomial time algorithm that has an approximation ratio smaller than formula_19, which can be proven by a reduction from the strongly NP -complete 3-partition problem. Note that both lower bounds formula_1 and formula_19 also hold for the case that a rotation of the items by 90 degrees is allowed. Additionally, it was proven by Ashok et al. that strip packing is W-hard when parameterized by the height of the optimal packing. Properties of optimal solutions. There are two trivial lower bounds on optimal solutions. The first is the height of the largest item. Define formula_22. Then it holds that formula_23. Another lower bound is given by the total area of the items. Define formula_24 then it holds that formula_25. 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 formula_26. For the first lower bound assume that the items are sorted by non-increasing height. Define formula_27. For each formula_28 define formula_29 the first index such that formula_30. Then it holds that formula_31. For the second lower bound, partition the set of items into three sets. Let formula_32 and define formula_33, formula_34, and formula_35. Then it holds that formula_36, where formula_37 for each formula_38. On the other hand, Steinberg has shown that  the height of an optimal solution can be upper bounded by formula_39 More precisely he showed that given a formula_40 and a formula_41 then the items formula_7 can be placed inside a box with width formula_43 and height formula_44 if formula_45, where formula_37. Polynomial time approximation algorithms. Since this problem is NP-hard, approximation algorithms have been studied for this problem. Most of the heuristic approaches have an approximation ratio between formula_47 and formula_48. Finding an algorithm with a ratio below formula_48 seems hard, and the complexity of the corresponding algorithms increases regarding their running time and their descriptions. The  smallest approximation ratio achieved so far is formula_50. Bottom-up left-justified (BL). This algorithm was first described by Baker et al. It works as follows: Let formula_51 be a sequence of rectangular items. The algorithm iterates the sequence in the given order. For each considered item formula_52, it searches for the bottom-most position to place it and then shifts it as far to the left as possible. Hence, it places formula_53 at the bottom-most left-most possible coordinate formula_54 in the strip. This algorithm has the following properties: Next-fit decreasing-height (NFDH). This algorithm was first  described by Coffman et al. in 1980 and works as follows: Let formula_72 be the given set of rectangular items. First, the algorithm sorts the items by order of nonincreasing height. Then, starting at position formula_73, 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: First-fit  decreasing-height (FFDH). 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 split-fit algorithm (SF). This algorithm was first described by Coffman et al. For a given set of items formula_72 and strip with width formula_104, it works as follows: This  algorithm has the following properties: Sleator's algorithm. For a given set of items formula_72 and strip with width formula_104, it works as follows: This algorithm has the following properties: The split algorithm (SP). 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 formula_149 side-by-side of an already placed item formula_150. In this case, it splits the corresponding sub-strip  into two pieces: one containing the first item formula_150 and the other containing the current item formula_149. If this is not possible, it places formula_149 on top of an already placed item and does not split the sub-strip. This algorithm creates a set <samp> S </samp> of sub-strips. For each sub-strip <samp> s ∈ S</samp> we know its lower left corner <samp> s.xposition</samp> and <samp> s.yposition</samp>, its width <samp> s.width</samp>, the horizontal lines parallel to the upper and lower border of  the item placed last inside this sub-strip <samp> s.upper</samp> and <samp> s.lower</samp>, as well as the width of it <samp> s.itemWidth</samp>. This algorithm has the following properties: Reverse-fit (RF). This algorithm was first described by Schiermeyer. The description of this algorithm needs some additional notation. For a placed item formula_8, its lower left corner is denoted by formula_166 and its upper right corner by formula_167. Given a set of items formula_7 and a strip of width formula_43, it works as follows: This algorithm has the following properties: Steinberg's  algorithm (ST). Steinbergs algorithm is a recursive one. Given a set of rectangular items formula_201 and a rectangular target region with width formula_104 and height formula_203, 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 formula_201 we denote by formula_205 the tallest item height in formula_201, formula_207 the largest item width appearing in formula_201 and by formula_209 the total area of these items. Steinbergs shows that if formula_210, formula_211, and formula_212, where  formula_213, then all the items can be placed inside the target region of size formula_214. 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 formula_215. Procedure 2: It can be applied if the following conditions hold: formula_232, formula_233, and there exist two different items formula_234 with formula_235, formula_236, formula_237, formula_238 and formula_239. Procedure 3: It can be applied if the following conditions hold : formula_232, formula_233, formula_248, and when sorting the items by decreasing width there exist an index formula_249 such that when defining formula_250 as the first formula_249 items it holds that formula_252 as well as formula_253 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: formula_232, formula_233, and there exists an item formula_8 such that formula_264. This algorithm has the following properties: Pseudo-polynomial time approximation algorithms. To improve upon the lower bound of formula_1 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 formula_43 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 formula_274. 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 formula_275. while there cannot be a pseudo-polynomial time algorithm with ratio better than formula_276 unless formula_2 Online algorithms. 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 formula_278, where formula_279 corresponds to the solution generated by the online algorithm and formula_280 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 formula_281 with formula_282 it is defined as formula_283. Note that all the instances  can be scaled such that formula_282. 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.