2491:
4509:
2166:
10503:
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
13959:
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
8999:
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,
828:
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
20:
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
5944:
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
28:
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
14358:
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,
5405:
855:
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.
2486:{\displaystyle OPT(I)\geq \max _{\alpha \in \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 \}}}
5471:, 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.
8796:
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
8467:
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
733:
11268:
14857:
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.
813:-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.
9000:
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);
13902:
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
10210:
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
12438:
2989:
9941:
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
12968:
13772:
6176:
4424:
4297:
8734:
5737:
9231:
8123:
2060:
1807:
2159:
6630:
6898:
6480:
11353:. 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.
10784:, 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
1955:
4038:
11025:
1298:
2688:
8961:
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;
7839:
534:
5931:
9521:
6754:
14657:
13119:
7959:
821:
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.
9360:
8550:
5552:
13529:
15609:
Bougeret, Marin; Dutot, Pierre-Francois; Jansen, Klaus; Robenek, Christina; Trystram, Denis (5 April 2012). "Approximation
Algorithms for Multiple Strip Packing and Scheduking Parallel Jobs in Platforms".
1145:
5313:
13923:
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
13293:
1373:
13863:
10709:
5393:
569:
11124:
3729:
11416:
3825:
800:
1501:
10584:
9065:
6004:
3583:
3414:
4170:
13411:
13357:
12743:
12689:
12039:
11985:
8597:
5599:
3321:
1642:
11119:
11073:
2736:
395:
342:
14432:
1864:
12080:
3121:
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
849:
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.
12581:
10910:
10846:
5176:
5060:
839:
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
14501:
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
14016:
10140:
4493:
1424:
7655:
7442:
7298:
7127:
3483:
1204:
2849:
12783:
9932:
7485:
7396:
7167:
7081:
5217:
13254:
12832:
11322:
3043:
2545:
205:
13441:
11580:
11450:
9560:
7197:
6373:
564:
425:
289:
14702:
14561:
14336:
14287:
14235:
14186:
14137:
13024:
12262:
12171:
11831:
11717:
11683:
4944:
4880:
3159:
2778:
127:
14790:
9389:
9260:
7987:
6986:
6780:
6506:
5817:
4729:
2573:
10618:
9099:
7353:
6038:
11628:
7252:
13799:
13648:
13577:
12628:
12511:
11652:
11517:
10934:
10870:
10806:
10742:
10645:
10333:
9679:
9439:
9284:
9126:
8785:
8624:
8156:
8011:
7707:
7041:
6934:
6804:
6657:
6530:
6280:
6227:
6065:
5841:
5788:
5626:
5437:
2802:
259:
10428:
9652:
9606:
12214:
12123:
11493:
10186:
7543:
6343:
5089:
4973:
4087:
14753:
6070:
4313:
4186:
12857:
1562:
12267:
11351:
9815:
8761:
6203:
5764:
8629:
14847:
13954:
13222:
12487:
11924:
11891:
11777:
10476:
10381:
10259:
10234:
7606:
6256:
5631:
3924:
3875:
3633:
3225:
14982:
14499:
13615:
9415:
4796:
4648:
4563:
1527:
13169:
11858:
11744:
11547:
10286:
9998:
9934:. 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
9879:
9845:
9785:
9758:
9131:
8465:
8438:
8383:
8356:
8295:
8262:
8235:
8016:
5469:
4761:
4615:
1960:
14464:
14073:
1649:
960:
931:
87:
15343:
Coffman Jr., Edward G.; Garey, M. R.; Johnson, David S.; Tarjan, Robert Endre (1980). "Performance Bounds for Level-Oriented Two-Dimensional
Packing Algorithms".
14044:
13900:
9968:
9731:
8992:
Place i at position (s.xposition, s.upper); Update s: s.lower := s.upper; s.upper := s.upper+i.height; s.itemWidth := i.width;
8411:
8326:
8208:
7865:
7014:
2065:
1055:
1027:
992:
902:
235:
155:
58:
14904:
14519:
13921:
13635:
13553:
13189:
13142:
12852:
12803:
12601:
12462:
11797:
10782:
10762:
10522:
10496:
10451:
10356:
10208:
10078:
10058:
10038:
10018:
9699:
8895:
8875:
8855:
8835:
8815:
8176:
7727:
7675:
7566:
6954:
6535:
6300:
5237:
5109:
4993:
4816:
4668:
4583:
4537:
3119:
3099:
3079:
2842:
2822:
6809:
6378:
15170:
Henning, Sören; Jansen, Klaus; Rau, Malin; Schmarje, Lars (2019). "Complexity and
Inapproximability Results for Parallel Task Scheduling and Strip Packing".
1869:
3940:
10939:
1212:
2583:
7732:
430:
32:
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
15695:. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 144. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. pp. 62:1–62:14.
6903:
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.
5935:
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.
5846:
1378:
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
16243:
9444:
6662:
15798:. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 65. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. pp. 9:1–9:14.
14568:
7870:
1057:
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
9289:
5319:
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
11833:
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
8297:
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.
8479:
5481:
13032:
872:
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
5439:
be the given set of rectangular items. First, the algorithm sorts the items by order of nonincreasing height. Then, starting at position
11926:
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.
9532:
This algorithm was first described by
Schiermeyer. The description of this algorithm needs some additional notation. For a placed item
16131:
Brown, Donna J.; Baker, Brenda S.; Katseff, Howard P. (1 November 1982). "Lower bounds for on-line two-dimensional packing algorithms".
15837:
Jansen, Klaus; Rau, Malin (29–31 March 2017). "Improved
Approximation for Two Dimensional Strip Packing with Polynomial Bounded Width".
13446:
1072:
5242:
1305:
802:. The objective is to find an overlapping-free packing of the items inside the strip while minimizing the height of the packing.
728:{\displaystyle \mathrm {inn} (i)=\{(x,y)\in \mathbb {Q} \times \mathbb {Q} |x_{i}<x<x_{i}+w_{i},y_{i}<y<y_{i}+h_{i}\}}
16293:
13804:
11263:{\displaystyle \mathrm {AREA} ({\mathcal {I}})\leq W\cdot H-(2h_{\max }({\mathcal {I}})-h)_{+}(2w_{\max }({\mathcal {I}})-W)_{+}}
10650:
5322:
13299:
Note that procedures 1 to 3 have a symmetric version when swapping the height and the width of the items and the target region.
16399:
15022:
Wäscher, Gerhard; Haußner, Heike; Schumann, Holger (16 December 2007). "An improved typology of cutting and packing problems".
3647:
16115:
16071:
15982:
15864:
15778:
15566:
15485:
13259:
12516:
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.
3743:
738:
4565:, it searches for the bottom-most position to place it and then shifts it as far to the left as possible. Hence, it places
1429:
9790:
Sort the remaining items in order of nonincreasing height and consider the items in this order in the following steps. Let
10535:
9016:
8997:
In this case, place the item next to another one at the same level and split the corresponding sub-strip at this position.
5955:
3496:
3335:
4103:
11362:
15506:
13362:
13308:
12694:
12640:
11990:
11936:
4539:
be a sequence of rectangular items. The algorithm iterates the sequence in the given order. For each considered item
8555:
5557:
3242:
1567:
15813:
15761:
Nadiradze, Giorgi; Wiese, Andreas (21 December 2015). "On approximating strip packing with a better ratio than 3/2".
15710:
15253:
Martello, Silvano; Monaci, Michele; Vigo, Daniele (1 August 2003). "An Exact
Approach to the Strip-Packing Problem".
11078:
11032:
2695:
347:
294:
4624:
The approximation ratio of this algorithm cannot be bounded by a constant. More precisely they showed that for each
15541:
Harren, Rolf; van Stee, Rob (2009). "Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems".
15436:
Baker, Brenda S; Brown, Donna J; Katseff, Howard P (December 1981). "A 5/4 algorithm for two-dimensional packing".
14367:
1815:
15582:
Jansen, Klaus; Solis-Oba, Roberto (August 2009). "Rectangle packing with one-dimensional resource augmentation".
11799:. Solve the problem consisting of this new target region and the reduced set of items with one of the procedures.
16389:
15888:
Baker, Brenda S.; Schwarz, Jerald S. (1 August 1983). "Shelf Algorithms for Two-Dimensional Packing Problems".
10875:
10811:
5114:
4998:
2984:{\displaystyle WH\geq 2\mathrm {AREA} ({\mathcal {I}})+(2w_{\max }({\mathcal {I}})-W)_{+}(2h_{\max }(I)-H)_{+}}
1069:
There are two trivial lower bounds on optimal solutions. The first is the height of the largest item. Define
13963:
10083:
4440:
1381:
15076:
Baker, Brenda S.; Coffman Jr., Edward G.; Rivest, Ronald L. (1980). "Orthogonal Packings in Two Dimensions".
7614:
7401:
7257:
7086:
3425:
1152:
89:. However, the best approximation ratio achieved so far (by a polynomial time algorithm by Harren et al.) is
15409:
Golan, Igal (August 1981). "Performance Bounds for Orthogonal Oriented Two-Dimensional Packing Algorithms".
12044:
8920:, the horizontal lines parallel to the upper and lower border of the item placed last inside this sub-strip
12748:
10358:
to the left until it touches another item or the border of the strip. Define the third level at the top of
9884:
7450:
7361:
7132:
7046:
5184:
3058:
12522:
11273:
8974:
I Define new list S_2 containing all the substrips with s.width - s.itemWidth ≥ i.width;
2994:
2496:
168:
13416:
11555:
11425:
9535:
7172:
6348:
539:
400:
264:
14665:
14524:
14301:
14252:
14200:
14151:
14102:
12973:
11805:
11691:
11657:
7490:
Reorder the levels/shelves constructed by FFDH such that all the shelves with a total width larger than
4888:
4824:
3124:
2741:
92:
15150:
14769:
13767:{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|)^{2}/\log(\log(|{\mathcal {I}}|)))}
9973:
Shift the second reverse-level down until an item from it touches an item from the first level. Define
9368:
9239:
7966:
6963:
6759:
6485:
5796:
4673:
2550:
16348:
Yu, Guosong; Mao, Yanling; Xiao, Jiaoliao (1 May 2016). "A new lower bound for online strip packing".
15959:
15504:; Rémila, Eric (November 2000). "A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem".
10589:
9070:
8837:. In this case, it splits the corresponding sub-strip into two pieces: one containing the first item
8267:
Sort all the remaining items in nonincreasing order of height. The items will be placed in this order.
7303:
6009:
2578:
On the other hand, Steinberg has shown that the height of an optimal solution can be upper bounded by
16394:
16185:
15923:
Csirik, János; Woeginger, Gerhard J. (28 August 1997). "Shelf algorithms for on-line strip packing".
13230:
13124:
Define two new rectangular target areas one at the lower-left corner of the original one with height
12808:
11585:
11522:
Sort them by nonincreasing width and place them left-aligned at the bottom of the target region. Let
7202:
15734:
Jansen, Klaus; Thöle, Ralf (January 2010). "Approximation Algorithms for Scheduling Parallel Jobs".
15090:
13780:
13558:
12609:
12492:
11633:
11498:
10915:
10851:
10787:
10723:
10626:
10296:
9660:
9420:
9265:
9107:
8766:
8605:
8137:
7992:
7688:
7022:
6915:
6785:
6638:
6511:
6261:
6208:
6171:{\displaystyle FFDH({\mathcal {I}})\leq 1.7OPT({\mathcal {I}})+h_{\max }\leq 2.7OPT({\mathcal {I}})}
6046:
5822:
5769:
5607:
5418:
4419:{\displaystyle (1+\varepsilon )OPT(I)+{\mathcal {O}}(\log(1/\varepsilon )/\varepsilon )h_{\max }(I)}
4292:{\displaystyle (1+\varepsilon )OPT(I)+{\mathcal {O}}(\log(1/\varepsilon )/\varepsilon )h_{\max }(I)}
2783:
240:
16102:. Lecture Notes in Computer Science. Vol. 2076. Springer Berlin Heidelberg. pp. 237–248.
16048:. Lecture Notes in Computer Science. Vol. 4508. Springer Berlin Heidelberg. pp. 358–367.
12963:{\displaystyle \mathrm {AREA} ({\mathcal {I}})-WH/4\leq \mathrm {AREA} ({\mathcal {I'}})\leq 3WH/8}
12219:
12128:
10391:
9611:
9565:
3054:
1058:
810:
735:. Two (placed) items overlap if they share an inner point. The height of the packing is defined as
15472:. Lecture Notes in Computer Science. Vol. 855. Springer Berlin Heidelberg. pp. 290–299.
12433:{\displaystyle 2(\mathrm {AREA} ({\mathcal {I}})-w(i)h(i)-w(i')h(i'))\leq (W-\max\{w(i),w(i')\})H}
12176:
12085:
11455:
10150:
8210:
and stack them at the bottom of the strip (in random order). Call the total height of these items
7493:
6305:
5068:
4952:
4054:
15969:. Lecture Notes in Computer Science. Vol. 4927. Springer Berlin Heidelberg. pp. 67–74.
14735:
8729:{\displaystyle A({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }/2\leq 2.5OPT({\mathcal {I}})}
873:
10498:
left-aligned in this third level, such that it touches an item from the first level on its left.
5732:{\displaystyle NFDH({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }\leq 3OPT({\mathcal {I}})}
1532:
15373:
Sleator, Daniel Dominic (1980). "A 2.5 Times Optimal Algorithm for Packing in Two Dimensions".
15085:
11330:
9793:
8739:
6181:
5742:
963:
806:
9226:{\displaystyle SP({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }\leq 3OPT({\mathcal {I}})}
8118:{\displaystyle SF({\mathcal {I}})>\left((m+2)/(m+1)-\varepsilon \right)OPT({\mathcal {I}})}
2055:{\displaystyle {\mathcal {I}}_{2}(\alpha ):=\{i\in {\mathcal {I}}|W-\alpha \geq w(i)>W/2\}}
1426:. For the first lower bound assume that the items are sorted by non-increasing height. Define
14832:
14359:
items may be repacked when another item arrives. This variant is called the migration model.
13927:
13194:
11896:
11863:
11749:
7571:
6235:
3891:
3842:
3600:
3192:
1802:{\displaystyle OPT(I)\geq \max\{h(l)+h(i(l))|l>k\wedge w(l)+\sum _{j=1}^{i(l)}w(j)>W\}}
16044:
Han, Xin; Iwama, Kazuo; Ye, Deshi; Zhang, Guochuan (2007). "Strip Packing vs. Bin Packing".
14967:
14469:
13585:
9394:
4766:
4627:
4542:
2154:{\displaystyle {\mathcal {I}}_{3}(\alpha ):=\{i\in {\mathcal {I}}|W/2\geq w(i)>\alpha \}}
1506:
15546:
15295:
Steinberg, A. (March 1997). "A Strip-Packing Algorithm with Absolute Performance Bound 2".
13147:
11836:
11722:
11525:
10264:
9976:
9857:
9823:
9763:
9736:
8443:
8416:
8361:
8334:
8273:
8240:
8213:
5442:
4734:
4588:
995:
14440:
14049:
6625:{\displaystyle FFDH({\mathcal {I}})>\left(1+1/m-\varepsilon \right)OPT({\mathcal {I}})}
936:
907:
63:
8:
15637:
Sviridenko, Maxim (January 2012). "A note on the Kenyon–Remila strip-packing algorithm".
14021:
13877:
9945:
9708:
8388:
8303:
8185:
7844:
6991:
1032:
1004:
998:
969:
879:
869:
214:
132:
35:
15550:
12467:
10456:
10361:
10239:
10214:
6893:{\displaystyle FFDH({\mathcal {I}})>\left(3/2-\varepsilon \right)OPT({\mathcal {I}})}
6475:{\displaystyle FFDH({\mathcal {I}})\leq \left(1+1/m\right)OPT({\mathcal {I}})+h_{\max }}
16274:
16224:
16166:
16077:
16049:
16023:
15870:
15842:
15819:
15716:
15669:
15543:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
15523:
15468:
Schiermeyer, Ingo (1994). "Reverse-Fit: A 2-optimal algorithm for packing rectangles".
15197:
15179:
14889:
14504:
13906:
13620:
13538:
13174:
13127:
12837:
12788:
12586:
12447:
11782:
10767:
10747:
10507:
10481:
10436:
10341:
10193:
10063:
10043:
10023:
10003:
9684:
8880:
8860:
8840:
8820:
8800:
8385:
the corresponding point on the right half. Draw two horizontal line segments of length
8161:
7712:
7660:
7551:
6939:
6285:
5222:
5094:
4978:
4801:
4653:
4568:
4522:
3104:
3084:
3064:
2827:
2807:
857:
15936:
12519:
Define a new target area on the right of these both items, such that it has the width
1950:{\displaystyle {\mathcal {I}}_{1}(\alpha ):=\{i\in {\mathcal {I}}|w(i)>W-\alpha \}}
129:, imposing an open question of whether there is an algorithm with approximation ratio
16365:
16330:
16266:
16216:
16158:
16111:
16067:
16015:
15998:
Ye, Deshi; Han, Xin; Zhang, Guochuan (1 May 2009). "A note on online strip packing".
15978:
15940:
15905:
15860:
15809:
15774:
15706:
15562:
15481:
15449:
15386:
15270:
15039:
9847:
until no other item fit on this shelf or there is no item left. Call this shelf the
4033:{\displaystyle (1+\varepsilon )OPT(I)+{\mathcal {O}}(1/\varepsilon ^{2})h_{\max }(I)}
16278:
16228:
16170:
16027:
15874:
15720:
15201:
11020:{\displaystyle \mathrm {AREA} ({\mathcal {I}}):=\sum _{i\in {\mathcal {I}}}w(i)h(i)}
1293:{\displaystyle \mathrm {AREA} ({\mathcal {I}}):=\sum _{i\in {\mathcal {I}}}h(i)w(i)}
16357:
16320:
16258:
16208:
16200:
16148:
16140:
16103:
16059:
16007:
15970:
15932:
15897:
15852:
15823:
15799:
15766:
15743:
15696:
15646:
15619:
15591:
15554:
15527:
15515:
15473:
15445:
15418:
15382:
15352:
15304:
15262:
15228:
15189:
15129:
15095:
15031:
14362:
The quality of an online algorithm is measured by the (absolute) competitive ratio
14355:
14018:. while there cannot be a pseudo-polynomial time algorithm with ratio better than
5412:
This algorithm was first described by Coffman et al. in 1980 and works as follows:
5219:, there exists an instance containing only squares where each order of the squares
2683:{\displaystyle OPT(I)\leq 2\max\{h_{\max }(I),\mathrm {AREA} ({\mathcal {I}})/W\}.}
15770:
15763:
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms
397:. A packing of the items is a mapping that maps each lower-left corner of an item
16063:
15856:
15804:
15595:
15558:
15134:
15117:
843:, and the strip is open-ended in one dimension and bounded in the residual ones.
840:
15974:
15519:
15266:
15215:
Ashok, Pradeesha; Kolay, Sudeshna; Meesum, S.M.; Saurabh, Saket (January 2017).
7834:{\displaystyle SF({\mathcal {I}})\leq (m+2)/(m+1)OPT({\mathcal {I}})+2h_{\max }}
529:{\displaystyle (x_{i},y_{i})\in (\cap \mathbb {Q} )\times \mathbb {Q} _{\geq 0}}
29:
fixed width but infinite length, and one wants to minimize the wasted material.
16361:
16081:
15701:
15501:
15193:
15035:
6912:
This algorithm was first described by Coffman et al. For a given set of items
16325:
16312:
16262:
16212:
16204:
16011:
15650:
15623:
15308:
15233:
15216:
16383:
16369:
16334:
16270:
16220:
16162:
16107:
16019:
15944:
15909:
15274:
15043:
9733:
on top of each other (in random order) at the bottom of the strip. Denote by
5926:{\displaystyle NFDH({\mathcal {I}}|)>(2-\varepsilon )OPT({\mathcal {I}}).}
15794:
Gálvez, Waldo; Grandoni, Fabrizio; Ingala, Salvatore; Khan, Arindam (2016).
13960:
using linear and dynamic programming. The best ratio accomplished so far is
4512:
An example of solutions generated by the Bottom-Up Left-Justified algorithm.
1812:
For the second lower bound, partition the set of items into three sets. Let
9516:{\displaystyle SP({\mathcal {I}})>(2-\varepsilon )OPT({\mathcal {I}})+C}
6749:{\displaystyle FFDH({\mathcal {I}})\leq (3/2)OPT({\mathcal {I}})+h_{\max }}
15116:
Harren, Rolf; Jansen, Klaus; Prädel, Lars; van Stee, Rob (February 2014).
14652:{\displaystyle \lim \mathrm {sup} _{OPT(I)\rightarrow \infty }A(I)/OPT(I)}
13637:
and place the residual items inside this area using one of the procedures.
10720:
Steinbergs algorithm is a recursive one. Given a set of rectangular items
7954:{\displaystyle SF({\mathcal {I}})\leq (3/2)OPT({\mathcal {I}})+2h_{\max }}
9355:{\displaystyle SP({\mathcal {I}})>(3-\varepsilon )OPT({\mathcal {I}})}
15841:. Lecture Notes in Computer Science. Vol. 10167. pp. 409–420.
8976:
S_2 contains all sub-strips where i fits next to the already placed item
4516:
This algorithm was first described by Baker et al. It works as follows:
16144:
15545:. Lecture Notes in Computer Science. Vol. 5687. pp. 177–189.
15477:
13582:
Define a new target area right of this item such that it has the width
11860:
be the total width of these items. Define a new target area with width
4885:
If the item are all squares and are ordered by decreasing widths, then
16153:
15765:. Society for Industrial and Applied Mathematics. pp. 1491–1510.
15747:
15217:"Parameterized complexity of Strip Packing and Minimum Volume Packing"
12785:, and when sorting the items by decreasing width there exist an index
8545:{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|))}
5547:{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|))}
16244:"Online scheduling of parallel jobs on two machines is 2-competitive"
13114:{\displaystyle W_{1}:=\max {W/2,2\mathrm {AREA} ({\mathcal {I'}})/H}}
1209:
Another lower bound is given by the total area of the items. Define
15901:
15422:
15356:
15099:
5404:
16054:
15847:
15674:
15184:
8897:
on top of an already placed item and does not split the sub-strip.
14466:
corresponds to the solution generated by the online algorithm and
13869:
11327:
then all the items can be placed inside the target region of size
9881:
be the height of the tallest unpacked item. Define a new shelf at
14862:
Overview of lower bounds for online algorithms without migration
13524:{\displaystyle w(i)h(i)\geq \mathrm {AREA} ({\mathcal {I}})-WH/4}
16313:"New lower bounds for certain classes of bin packing algorithms"
15960:"Online Algorithm for Parallel Job Scheduling and Strip Packing"
6988:, the largest integer such that the given rectangles have width
805:
This definition is used for all polynomial time algorithms. For
16098:
Seiden, Steven S. (2001). "On the Online Bin Packing Problem".
15796:
Improved Pseudo-Polynomial-Time Approximation for Strip Packing
13555:
in the lower-left corner of the target area and remove it from
9760:
the height of this stack. All other items will be packed above
16311:
Balogh, János; Békési, József; Galambos, Gábor (6 July 2012).
9820:
Place the items one by one left aligned on a shelf defined by
8358:
be the highest point covered by any item in the left half and
4508:
1140:{\displaystyle h_{\max }(I):=\max\{h(i)|i\in {\mathcal {I}}\}}
15342:
5308:{\displaystyle BL(L)/OPT(L)>{\frac {12}{11+\varepsilon }}}
4763:
is the height of the packing created by the BL algorithm and
7608:, next to more narrow levels/shelves, that contains no item.
1368:{\displaystyle OPT(I)\geq \mathrm {AREA} ({\mathcal {I}})/W}
829:
have been studied. In the latter case, it is referred to as
13858:{\displaystyle ST({\mathcal {I}})\leq 2OPT({\mathcal {I}})}
10704:{\displaystyle RF({\mathcal {I}})\leq 2OPT({\mathcal {I}})}
5388:{\displaystyle BL(L)/OPT(L)>{\frac {4}{3+\varepsilon }}}
4670:
of rectangular items ordered by increasing width such that
3048:
15608:
15115:
14343:
also for 90 degree rotations and contiguous moldable jobs
11719:
is empty, define the new target region as the area above
11027:
the total area of these items. Steinbergs shows that if
5408:
An example for NFDH and FFDH applied to the same instance
1061:
when parameterized by the height of the optimal packing.
15793:
15169:
3724:{\displaystyle (4/3)OPT(I)+7{\frac {1}{18}}h_{\max }(I)}
15666:
The Bottom-Left Algorithm for the Strip Packing Problem
15214:
15151:"The Two-Dimensional Rectangular Strip Packing Problem"
13288:{\displaystyle {\mathcal {I}}\setminus {\mathcal {I'}}}
10000:
as the new vertical position of the shifted shelf. Let
3820:{\displaystyle (5/4)OPT(I)+6{\frac {7}{8}}h_{\max }(I)}
966:
algorithm that has an approximation ratio smaller than
795:{\displaystyle \max\{y_{i}+h_{i}|i\in {\mathcal {I}}\}}
15075:
15021:
14989:
lower bound due to the underlying bin packing problem
13305:: It can be applied if the following conditions hold:
12637:: It can be applied if the following conditions hold:
11933:: It can be applied if the following conditions hold:
9817:
be the height of the tallest of these remaining items.
1496:{\displaystyle k:=\max\{i:\sum _{j=1}^{k}w(j)\leq W\}}
14970:
14892:
14835:
14772:
14738:
14668:
14571:
14527:
14507:
14472:
14443:
14370:
14304:
14255:
14203:
14154:
14105:
14052:
14024:
13966:
13930:
13909:
13880:
13807:
13783:
13651:
13623:
13588:
13561:
13541:
13449:
13419:
13365:
13311:
13262:
13233:
13197:
13177:
13150:
13130:
13035:
12976:
12860:
12840:
12811:
12791:
12751:
12697:
12643:
12630:
into the new target area using one of the procedures.
12612:
12589:
12525:
12495:
12470:
12450:
12270:
12222:
12179:
12131:
12088:
12047:
11993:
11939:
11899:
11866:
11839:
11808:
11785:
11752:
11725:
11694:
11660:
11636:
11588:
11558:
11528:
11501:
11458:
11428:
11365:
11333:
11276:
11127:
11081:
11035:
10942:
10918:
10878:
10854:
10814:
10790:
10770:
10750:
10726:
10653:
10629:
10592:
10538:
10510:
10484:
10459:
10439:
10394:
10364:
10344:
10299:
10267:
10242:
10217:
10196:
10153:
10086:
10066:
10046:
10026:
10006:
9979:
9948:
9887:
9860:
9826:
9796:
9766:
9739:
9711:
9687:
9663:
9614:
9568:
9538:
9447:
9423:
9397:
9371:
9292:
9268:
9242:
9134:
9110:
9073:
9019:
8883:
8863:
8843:
8823:
8803:
8769:
8742:
8632:
8608:
8558:
8482:
8446:
8419:
8391:
8364:
8337:
8306:
8276:
8243:
8216:
8188:
8164:
8140:
8019:
7995:
7969:
7873:
7847:
7735:
7715:
7691:
7663:
7617:
7574:
7554:
7496:
7453:
7404:
7364:
7306:
7260:
7205:
7175:
7135:
7089:
7049:
7025:
6994:
6966:
6942:
6918:
6812:
6788:
6762:
6665:
6641:
6538:
6514:
6488:
6381:
6351:
6308:
6288:
6264:
6238:
6211:
6184:
6073:
6049:
6012:
5958:
5939:
5849:
5825:
5799:
5772:
5745:
5634:
5610:
5560:
5484:
5445:
5421:
5325:
5245:
5225:
5187:
5117:
5097:
5071:
5001:
4995:
of rectangles ordered by decreasing widths such that
4981:
4955:
4891:
4827:
4804:
4769:
4737:
4676:
4656:
4630:
4591:
4571:
4545:
4525:
4443:
4316:
4189:
4106:
4057:
3943:
3894:
3845:
3746:
3650:
3603:
3499:
3428:
3338:
3245:
3195:
3127:
3107:
3087:
3067:
2997:
2852:
2830:
2810:
2786:
2744:
2698:
2586:
2553:
2499:
2169:
2068:
1963:
1872:
1818:
1652:
1570:
1535:
1509:
1432:
1384:
1308:
1215:
1155:
1075:
1035:
1007:
972:
939:
910:
882:
741:
572:
542:
433:
403:
350:
297:
267:
243:
217:
171:
135:
95:
66:
38:
16310:
16294:"A note on the lower bound for online strip packing"
14942:
also holds for the parallel task scheduling problem
14926:
also holds for the parallel task scheduling problem
14662:
Note that all the instances can be scaled such that
10579:{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|^{2})}
9060:{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|^{2})}
5999:{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|^{2})}
5399:
4821:
If the items are ordered by decreasing widths, then
3578:{\displaystyle 2OPT(I)+h_{\max }(I)/2\leq 2.5OPT(I)}
3409:{\displaystyle 1.7OPT(I)+h_{\max }(I)\leq 2.7OPT(I)}
856:
Packings that allow this kind of cutting are called
16186:"Scheduling parallel jobs to minimize the makespan"
15693:
Closing the Gap for Pseudo-Polynomial Strip Packing
15118:"A (5/3 + epsilon)-approximation for strip packing"
10504:side, but an item from the first level or the item
10288:as the amount by which the shelf was shifted down.
8986:
In this case, place the item on top of another one.
4165:{\displaystyle (1+\varepsilon )OPT(I)+h_{\max }(I)}
536:inside the strip. An inner point of a placed item
15252:
14976:
14898:
14841:
14784:
14747:
14696:
14651:
14555:
14513:
14493:
14458:
14426:
14330:
14281:
14229:
14180:
14131:
14078:Overview of pseudo-polynomial time approximations
14067:
14038:
14010:
13948:
13915:
13894:
13857:
13793:
13766:
13629:
13609:
13571:
13547:
13523:
13435:
13405:
13351:
13287:
13248:
13216:
13183:
13163:
13136:
13113:
13018:
12962:
12846:
12826:
12797:
12777:
12737:
12683:
12622:
12595:
12575:
12505:
12481:
12456:
12432:
12256:
12208:
12165:
12117:
12074:
12033:
11979:
11918:
11885:
11852:
11825:
11791:
11771:
11738:
11711:
11677:
11646:
11622:
11574:
11541:
11511:
11487:
11444:
11411:{\displaystyle w_{\max }({\mathcal {I}}')\geq W/2}
11410:
11345:
11316:
11262:
11113:
11067:
11019:
10928:
10904:
10864:
10840:
10800:
10776:
10756:
10736:
10703:
10639:
10612:
10578:
10516:
10490:
10470:
10445:
10422:
10375:
10350:
10327:
10280:
10253:
10228:
10202:
10180:
10134:
10072:
10052:
10032:
10012:
9992:
9962:
9926:
9873:
9839:
9809:
9779:
9752:
9725:
9693:
9673:
9646:
9600:
9554:
9515:
9433:
9409:
9383:
9354:
9278:
9254:
9225:
9120:
9093:
9059:
8889:
8869:
8849:
8829:
8809:
8779:
8755:
8728:
8618:
8591:
8544:
8459:
8432:
8405:
8377:
8350:
8320:
8289:
8256:
8229:
8202:
8170:
8150:
8117:
8005:
7981:
7953:
7859:
7833:
7721:
7701:
7669:
7649:
7600:
7560:
7537:
7479:
7436:
7390:
7347:
7292:
7246:
7191:
7161:
7121:
7075:
7035:
7008:
6980:
6948:
6928:
6892:
6798:
6774:
6748:
6651:
6624:
6524:
6500:
6474:
6367:
6337:
6294:
6274:
6250:
6221:
6197:
6170:
6059:
6032:
5998:
5925:
5835:
5811:
5782:
5758:
5731:
5620:
5593:
5546:
5463:
5431:
5387:
5307:
5231:
5211:
5170:
5111:of squares ordered by decreasing widths such that
5103:
5083:
5054:
4987:
4967:
4938:
4874:
4810:
4790:
4755:
4723:
4662:
4642:
4609:
4577:
4557:
4531:
4487:
4418:
4291:
4164:
4081:
4032:
3918:
3869:
3819:
3723:
3627:
3577:
3477:
3408:
3315:
3219:
3153:
3113:
3093:
3073:
3037:
2983:
2836:
2816:
2796:
2772:
2730:
2682:
2567:
2539:
2485:
2153:
2054:
1949:
1858:
1801:
1636:
1556:
1521:
1495:
1418:
1367:
1292:
1198:
1139:
1064:
1049:
1021:
986:
954:
925:
896:
794:
727:
558:
528:
419:
389:
336:
283:
253:
229:
199:
149:
121:
81:
52:
16130:
16046:Algorithmic Aspects in Information and Management
15663:
15612:Discrete Mathematics, Algorithms and Applications
15435:
13406:{\displaystyle h_{\max }({\mathcal {I}})\leq H/2}
13352:{\displaystyle w_{\max }({\mathcal {I}})\leq W/2}
12738:{\displaystyle h_{\max }({\mathcal {I}})\leq H/2}
12684:{\displaystyle w_{\max }({\mathcal {I}})\leq W/2}
12034:{\displaystyle h_{\max }({\mathcal {I}})\leq H/2}
11980:{\displaystyle w_{\max }({\mathcal {I}})\leq W/2}
8988:Find the sub-strip s in S with smallest s.upper;
4585:at the bottom-most left-most possible coordinate
3057:have been studied for this problem. Most of the
2478:
2237:
16381:
15686:
15684:
15664:Hougardy, Stefan; Zondervan, Bart (2024-02-26),
14708:Overview of online algorithms without migration
14674:
14572:
14533:
13371:
13317:
13256:into the first new target area and the items in
13227:Use one of the procedures to place the items in
13049:
12703:
12649:
12532:
12383:
11999:
11945:
11371:
11296:
11226:
11181:
11087:
11041:
10884:
10820:
10100:
9906:
9802:
9190:
8748:
8685:
8592:{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|)}
7946:
7826:
6741:
6467:
6190:
6135:
5751:
5696:
5594:{\displaystyle {\mathcal {O}}(|{\mathcal {I}}|)}
4503:
4402:
4275:
4148:
4016:
3803:
3707:
3529:
3461:
3368:
3316:{\displaystyle 2OPT(I)+h_{\max }(I)\leq 3OPT(I)}
3275:
3017:
2951:
2906:
2756:
2710:
2622:
2611:
2519:
2192:
1674:
1637:{\displaystyle w(l)+\sum _{j=1}^{i(l)}w(j)>W}
1439:
1182:
1098:
1081:
742:
16242:Hurink, J. L.; Paulus, J. J. (1 January 2008).
16093:
16091:
16043:
15922:
15581:
15248:
15246:
15244:
13870:Pseudo-polynomial time approximation algorithms
11114:{\displaystyle w_{\max }({\mathcal {I}})\leq W}
11068:{\displaystyle h_{\max }({\mathcal {I}})\leq H}
9705:Stack all the rectangles of width greater than
6907:
2731:{\displaystyle W\geq w_{\max }({\mathcal {I}})}
390:{\displaystyle h_{i}\in (0,1]\cap \mathbb {Q} }
337:{\displaystyle w_{i}\in (0,1]\cap \mathbb {Q} }
15760:
15540:
15463:
15461:
15459:
15338:
10040:be the right most pair of touching items with
994:, which can be proven by a reduction from the
15958:Hurink, Johann L.; Paulus, Jacob Jan (2007).
15681:
15336:
15334:
15332:
15330:
15328:
15326:
15324:
15322:
15320:
15318:
15148:
14427:{\displaystyle \mathrm {sup} _{I}A(I)/OPT(I)}
13641:This algorithm has the following properties:
10715:
10528:This algorithm has the following properties:
9009:This algorithm has the following properties:
8472:This algorithm has the following properties:
8328:, which cuts the strip into two equal halves.
7681:This algorithm has the following properties:
5948:This algorithm has the following properties:
5474:This algorithm has the following properties:
4620:This algorithm has the following properties:
876:that has an approximation ratio smaller than
16241:
16088:
16039:
16037:
15957:
15887:
15881:
15500:
15494:
15241:
12570:
12535:
12421:
12386:
11311:
11299:
9067:since the number of substrips is bounded by
8552:and if the items are already sorted even by
8182:Find all the items with a width larger than
7611:Use the FFDH algorithm to pack the items in
5554:and if the items are already sorted even by
5315:, i.e., there exist instances where BL does
3032:
3020:
2674:
2614:
2534:
2522:
2148:
2095:
2049:
1990:
1944:
1899:
1859:{\displaystyle \alpha \in \cap \mathbb {N} }
1796:
1677:
1490:
1442:
1134:
1101:
789:
745:
722:
596:
15733:
15467:
15456:
15290:
15288:
15286:
15284:
15071:
15069:
15067:
15065:
15063:
15061:
15059:
15057:
15055:
15053:
10744:and a rectangular target region with width
8791:
8237:. All the other items will be placed above
3165:Overview of polynomial time approximations
3101:. Finding an algorithm with a ratio below
16291:
15997:
15636:
15368:
15366:
15315:
8857:and the other containing the current item
4798:is the height of the optimal solution for
16347:
16324:
16152:
16053:
16034:
15846:
15836:
15803:
15700:
15690:
15673:
15294:
15232:
15183:
15165:
15163:
15133:
15089:
10905:{\displaystyle w_{\max }({\mathcal {I}})}
10841:{\displaystyle h_{\max }({\mathcal {I}})}
6974:
5171:{\displaystyle BL(L)/OPT(L)>2-\delta }
5055:{\displaystyle BL(L)/OPT(L)>3-\delta }
2561:
2229:
1852:
626:
618:
513:
501:
383:
330:
16350:European Journal of Operational Research
16292:Kern, Walter; Paulus, Jacob Jan (2009).
16183:
15404:
15402:
15400:
15398:
15396:
15281:
15111:
15109:
15050:
15024:European Journal of Operational Research
14011:{\displaystyle (5/4+\varepsilon )OPT(I)}
10135:{\displaystyle x_{r}:=\max(b_{f},b_{s})}
5403:
4507:
4488:{\displaystyle (5/3+\varepsilon )OPT(I)}
3049:Polynomial time approximation algorithms
1419:{\displaystyle {\mathcal {O}}(n\log(n))}
15372:
15363:
8817:side-by-side of an already placed item
7650:{\displaystyle {\mathcal {I}}_{narrow}}
7437:{\displaystyle {\mathcal {I}}_{narrow}}
7293:{\displaystyle {\mathcal {I}}_{narrow}}
7122:{\displaystyle {\mathcal {I}}_{narrow}}
3478:{\displaystyle 1.5OPT(I)+2h_{\max }(I)}
1199:{\displaystyle OPT(I)\geq h_{\max }(I)}
868:The strip packing problem contains the
16382:
16097:
15160:
12075:{\displaystyle i,i'\in {\mathcal {I}}}
12041:, and there exist two different items
9562:, its lower left corner is denoted by
8129:
2804:can be placed inside a box with width
2692:More precisely he showed that given a
237:and infinite height, as well as a set
16000:Journal of Combinatorial Optimization
15408:
15393:
15106:
13171:and the other left of it with height
12778:{\displaystyle |{\mathcal {I}}|>1}
10912:the largest item width appearing in
10453:define the third level at the top of
9927:{\displaystyle H_{0}+h_{\max }+h_{1}}
8877:. If this is not possible, it places
7480:{\displaystyle {\mathcal {I}}_{wide}}
7391:{\displaystyle {\mathcal {I}}_{wide}}
7162:{\displaystyle {\mathcal {I}}_{wide}}
7076:{\displaystyle {\mathcal {I}}_{wide}}
5212:{\displaystyle \varepsilon \in (0,1]}
14349:
12576:{\displaystyle W-\max\{w(i),w(i')\}}
11317:{\displaystyle (a)_{+}:=\max\{0,a\}}
10080:on the second reverse-level. Define
8763:is the largest height of an item in
6205:is the largest height of an item in
5766:is the largest height of an item in
3061:have an approximation ratio between
3038:{\displaystyle (x)_{+}:=\max\{x,0\}}
2540:{\displaystyle (x)_{+}:=\max\{x,0\}}
200:{\displaystyle I=({\mathcal {I}},W)}
16100:Automata, Languages and Programming
15967:Approximation and Online Algorithms
13874:To improve upon the lower bound of
13645:The running time can be bounded by
13436:{\displaystyle i\in {\mathcal {I}}}
11575:{\displaystyle i\in {\mathcal {I}}}
11445:{\displaystyle i\in {\mathcal {I}}}
10532:The running time can be bounded by
9555:{\displaystyle i\in {\mathcal {I}}}
9527:
9013:The running time can be bounded by
8476:The running time can be bounded by
7192:{\displaystyle i\in {\mathcal {I}}}
6508:, there exists such a set of items
6368:{\displaystyle i\in {\mathcal {I}}}
5952:The running time can be bounded by
5478:The running time can be bounded by
3330:First-Fit Decreasing-Height (FFDH)
559:{\displaystyle i\in {\mathcal {I}}}
420:{\displaystyle i\in {\mathcal {I}}}
284:{\displaystyle i\in {\mathcal {I}}}
13:
16184:Johannes, Berit (1 October 2006).
15839:WALCOM: Algorithms and Computation
15691:Jansen, Klaus; Rau, Malin (2019).
15507:Mathematics of Operations Research
14697:{\displaystyle h_{\max }(I)\leq 1}
14609:
14583:
14580:
14577:
14556:{\displaystyle h_{\max }(I)\leq 1}
14379:
14376:
14373:
14331:{\displaystyle (5/4+\varepsilon )}
14282:{\displaystyle (4/3+\varepsilon )}
14230:{\displaystyle (4/3+\varepsilon )}
14181:{\displaystyle (7/5+\varepsilon )}
14132:{\displaystyle (3/2+\varepsilon )}
13847:
13819:
13786:
13745:
13695:
13669:
13654:
13564:
13496:
13487:
13484:
13481:
13478:
13428:
13381:
13327:
13276:
13265:
13237:
13090:
13080:
13077:
13074:
13071:
13019:{\displaystyle w(i_{m+1})\leq W/4}
12928:
12918:
12915:
12912:
12909:
12880:
12871:
12868:
12865:
12862:
12815:
12759:
12713:
12659:
12615:
12498:
12296:
12287:
12284:
12281:
12278:
12067:
12009:
11955:
11826:{\displaystyle {\mathcal {I}}_{H}}
11812:
11712:{\displaystyle {\mathcal {I}}_{H}}
11698:
11678:{\displaystyle {\mathcal {I}}_{H}}
11664:
11639:
11567:
11504:
11437:
11382:
11236:
11191:
11147:
11138:
11135:
11132:
11129:
11097:
11051:
10986:
10962:
10953:
10950:
10947:
10944:
10921:
10894:
10857:
10830:
10793:
10729:
10693:
10665:
10632:
10600:
10556:
10541:
9666:
9547:
9499:
9459:
9426:
9344:
9304:
9271:
9215:
9174:
9146:
9113:
9081:
9037:
9022:
8904:of sub-strips. For each sub-strip
8772:
8718:
8669:
8641:
8611:
8576:
8561:
8526:
8500:
8485:
8143:
8107:
8031:
7998:
7927:
7885:
7807:
7747:
7694:
7621:
7457:
7408:
7368:
7264:
7184:
7139:
7093:
7053:
7028:
6921:
6882:
6830:
6791:
6725:
6683:
6644:
6614:
6556:
6517:
6451:
6399:
6360:
6267:
6214:
6160:
6119:
6091:
6052:
6020:
5976:
5961:
5940:First-fit decreasing-height (FFDH)
5912:
5867:
5828:
5775:
5721:
5680:
5652:
5628:, it produces a packing of height
5613:
5578:
5563:
5528:
5502:
5487:
5424:
4939:{\displaystyle BL(L)/OPT(L)\leq 2}
4875:{\displaystyle BL(L)/OPT(L)\leq 3}
4355:
4228:
3982:
3237:Next-Fit Decreasing-Height (NFDH)
3154:{\displaystyle (5/3+\varepsilon )}
2916:
2884:
2875:
2872:
2869:
2866:
2789:
2773:{\displaystyle H\geq h_{\max }(I)}
2720:
2658:
2649:
2646:
2643:
2640:
2401:
2340:
2282:
2256:
2106:
2072:
2001:
1967:
1910:
1876:
1387:
1349:
1340:
1337:
1334:
1331:
1259:
1235:
1226:
1223:
1220:
1217:
1129:
784:
580:
577:
574:
551:
412:
276:
246:
183:
122:{\displaystyle (5/3+\varepsilon )}
14:
16411:
14785:{\displaystyle 1.69+\varepsilon }
13270:
9384:{\displaystyle \varepsilon >0}
9255:{\displaystyle \varepsilon >0}
7982:{\displaystyle \varepsilon >0}
6981:{\displaystyle m\in \mathbb {N} }
6775:{\displaystyle \varepsilon >0}
6501:{\displaystyle \varepsilon >0}
5819:there exists a set of rectangles
5812:{\displaystyle \varepsilon >0}
5400:Next-fit decreasing-height (NFDH)
4724:{\displaystyle BL(L)/OPT(L)>M}
2568:{\displaystyle x\in \mathbb {R} }
261:of rectangular items. Each item
15149:Neuenfeldt Junior, Alvaro Luiz.
13801:it produces a packing of height
10647:it produces a packing of height
10613:{\displaystyle |{\mathcal {I}}|}
9094:{\displaystyle |{\mathcal {I}}|}
8626:it produces a packing of height
8270:Consider the horizontal line at
7348:{\displaystyle w(i)\leq W/(m+1)}
6782:, there exists a set of squares
6067:it produces a packing of height
6033:{\displaystyle |{\mathcal {I}}|}
16341:
16304:
16285:
16235:
16177:
16124:
15991:
15951:
15916:
15830:
15787:
15754:
15727:
15657:
15630:
15602:
15575:
15534:
15429:
14239:Gálvez, Grandoni, Ingala, Khan
13249:{\displaystyle {\mathcal {I'}}}
12827:{\displaystyle {\mathcal {I'}}}
11623:{\displaystyle h(i)>H-h_{0}}
8990:i.e. the least filled sub-strip
7548:This leaves a rectangular area
7545:are below the more narrow ones.
7247:{\displaystyle w(i)>W/(m+1)}
3053:Since this problem is NP-hard,
1065:Properties of optimal solutions
211:consists of a strip with width
15925:Information Processing Letters
15639:Information Processing Letters
15208:
15142:
15015:
14685:
14679:
14646:
14640:
14623:
14617:
14606:
14603:
14597:
14544:
14538:
14488:
14482:
14453:
14447:
14421:
14415:
14398:
14392:
14325:
14305:
14276:
14256:
14224:
14204:
14175:
14155:
14126:
14106:
14005:
13999:
13987:
13967:
13943:
13937:
13852:
13842:
13824:
13814:
13794:{\displaystyle {\mathcal {I}}}
13761:
13758:
13755:
13751:
13739:
13735:
13726:
13706:
13701:
13689:
13685:
13675:
13663:
13659:
13604:
13598:
13572:{\displaystyle {\mathcal {I}}}
13501:
13491:
13471:
13465:
13459:
13453:
13386:
13376:
13332:
13322:
13099:
13084:
12999:
12980:
12937:
12922:
12885:
12875:
12765:
12753:
12718:
12708:
12664:
12654:
12623:{\displaystyle {\mathcal {I}}}
12567:
12556:
12547:
12541:
12506:{\displaystyle {\mathcal {I}}}
12424:
12418:
12407:
12398:
12392:
12374:
12368:
12365:
12354:
12348:
12337:
12328:
12322:
12316:
12310:
12301:
12291:
12274:
12237:
12226:
12189:
12183:
12146:
12135:
12098:
12092:
12014:
12004:
11960:
11950:
11647:{\displaystyle {\mathcal {I}}}
11598:
11592:
11512:{\displaystyle {\mathcal {I}}}
11468:
11462:
11391:
11376:
11284:
11277:
11251:
11241:
11231:
11215:
11206:
11196:
11186:
11170:
11152:
11142:
11102:
11092:
11056:
11046:
11014:
11008:
11002:
10996:
10967:
10957:
10929:{\displaystyle {\mathcal {I}}}
10899:
10889:
10865:{\displaystyle {\mathcal {I}}}
10835:
10825:
10801:{\displaystyle {\mathcal {I}}}
10737:{\displaystyle {\mathcal {I}}}
10698:
10688:
10670:
10660:
10640:{\displaystyle {\mathcal {I}}}
10606:
10594:
10573:
10563:
10550:
10546:
10417:
10411:
10328:{\displaystyle h_{2}\leq h(s)}
10322:
10316:
10129:
10103:
10060:placed on the first level and
9674:{\displaystyle {\mathcal {I}}}
9641:
9615:
9608:and its upper right corner by
9595:
9569:
9504:
9494:
9482:
9470:
9464:
9454:
9434:{\displaystyle {\mathcal {I}}}
9417:, there exists a set of items
9349:
9339:
9327:
9315:
9309:
9299:
9279:{\displaystyle {\mathcal {I}}}
9262:, there exists a set of items
9220:
9210:
9179:
9169:
9151:
9141:
9121:{\displaystyle {\mathcal {I}}}
9087:
9075:
9054:
9044:
9031:
9027:
8908:we know its lower left corner
8780:{\displaystyle {\mathcal {I}}}
8723:
8713:
8674:
8664:
8646:
8636:
8619:{\displaystyle {\mathcal {I}}}
8586:
8582:
8570:
8566:
8539:
8536:
8532:
8520:
8516:
8506:
8494:
8490:
8151:{\displaystyle {\mathcal {I}}}
8112:
8102:
8079:
8067:
8059:
8047:
8036:
8026:
8006:{\displaystyle {\mathcal {I}}}
7932:
7922:
7910:
7896:
7890:
7880:
7812:
7802:
7790:
7778:
7770:
7758:
7752:
7742:
7702:{\displaystyle {\mathcal {I}}}
7595:
7583:
7532:
7520:
7512:
7500:
7342:
7330:
7316:
7310:
7241:
7229:
7215:
7209:
7036:{\displaystyle {\mathcal {I}}}
6929:{\displaystyle {\mathcal {I}}}
6887:
6877:
6835:
6825:
6799:{\displaystyle {\mathcal {I}}}
6730:
6720:
6708:
6694:
6688:
6678:
6652:{\displaystyle {\mathcal {I}}}
6619:
6609:
6561:
6551:
6525:{\displaystyle {\mathcal {I}}}
6456:
6446:
6404:
6394:
6318:
6312:
6275:{\displaystyle {\mathcal {I}}}
6222:{\displaystyle {\mathcal {I}}}
6165:
6155:
6124:
6114:
6096:
6086:
6060:{\displaystyle {\mathcal {I}}}
6026:
6014:
5993:
5983:
5970:
5966:
5917:
5907:
5895:
5883:
5877:
5873:
5862:
5836:{\displaystyle {\mathcal {I}}}
5783:{\displaystyle {\mathcal {I}}}
5726:
5716:
5685:
5675:
5657:
5647:
5621:{\displaystyle {\mathcal {I}}}
5588:
5584:
5572:
5568:
5541:
5538:
5534:
5522:
5518:
5508:
5496:
5492:
5458:
5446:
5432:{\displaystyle {\mathcal {I}}}
5361:
5355:
5338:
5332:
5281:
5275:
5258:
5252:
5206:
5194:
5153:
5147:
5130:
5124:
5037:
5031:
5014:
5008:
4927:
4921:
4904:
4898:
4863:
4857:
4840:
4834:
4785:
4779:
4750:
4744:
4712:
4706:
4689:
4683:
4604:
4592:
4482:
4476:
4464:
4444:
4413:
4407:
4394:
4383:
4369:
4360:
4347:
4341:
4329:
4317:
4286:
4280:
4267:
4256:
4242:
4233:
4220:
4214:
4202:
4190:
4159:
4153:
4137:
4131:
4119:
4107:
4076:
4070:
4027:
4021:
4008:
3987:
3974:
3968:
3956:
3944:
3913:
3907:
3864:
3858:
3814:
3808:
3779:
3773:
3761:
3747:
3718:
3712:
3683:
3677:
3665:
3651:
3622:
3616:
3572:
3566:
3540:
3534:
3518:
3512:
3472:
3466:
3447:
3441:
3403:
3397:
3379:
3373:
3357:
3351:
3310:
3304:
3286:
3280:
3264:
3258:
3214:
3208:
3148:
3128:
3005:
2998:
2972:
2962:
2956:
2940:
2931:
2921:
2911:
2895:
2889:
2879:
2797:{\displaystyle {\mathcal {I}}}
2767:
2761:
2725:
2715:
2663:
2653:
2633:
2627:
2602:
2596:
2507:
2500:
2456:
2450:
2444:
2441:
2435:
2423:
2418:
2412:
2381:
2375:
2369:
2363:
2357:
2351:
2313:
2307:
2299:
2293:
2273:
2267:
2222:
2202:
2185:
2179:
2139:
2133:
2112:
2089:
2083:
2032:
2026:
2007:
1984:
1978:
1929:
1923:
1916:
1893:
1887:
1845:
1825:
1787:
1781:
1773:
1767:
1742:
1736:
1717:
1713:
1710:
1704:
1698:
1689:
1683:
1668:
1662:
1625:
1619:
1611:
1605:
1580:
1574:
1545:
1539:
1481:
1475:
1413:
1410:
1404:
1392:
1354:
1344:
1324:
1318:
1287:
1281:
1275:
1269:
1240:
1230:
1193:
1187:
1171:
1165:
1117:
1113:
1107:
1092:
1086:
1001:. Note that both lower bounds
772:
631:
611:
599:
590:
584:
505:
494:
469:
466:
460:
434:
376:
364:
323:
311:
254:{\displaystyle {\mathcal {I}}}
194:
178:
116:
96:
1:
16400:Strongly NP-complete problems
15937:10.1016/S0020-0190(97)00120-8
15771:10.1137/1.9781611974331.ch102
15008:
14242:also for 90 degree rotations
12257:{\displaystyle h(i')\geq H/4}
12166:{\displaystyle w(i')\geq W/4}
10423:{\displaystyle h_{2}>h(s)}
9647:{\displaystyle (b_{i},d_{i})}
9601:{\displaystyle (a_{i},c_{i})}
8928:, as well as the width of it
8900:This algorithm creates a set
4504:Bottom-up left-justified (BL)
3187:Bottom-Up Left-Justified (BL)
160:
16317:Theoretical Computer Science
16064:10.1007/978-3-540-72870-2_34
15857:10.1007/978-3-319-53925-6_32
15805:10.4230/LIPIcs.FSTTCS.2016.9
15596:10.1016/j.disopt.2009.04.001
15559:10.1007/978-3-642-03685-9_14
15450:10.1016/0196-6774(81)90034-1
15387:10.1016/0020-0190(80)90121-0
15255:INFORMS Journal on Computing
15221:Theoretical Computer Science
15135:10.1016/j.comgeo.2013.08.008
14873:Asymptotic Competitive Ratio
14719:Asymptotic Competitive Ratio
12606:Place the residual items in
12209:{\displaystyle h(i)\geq H/4}
12118:{\displaystyle w(i)\geq W/4}
11654:and place them in a new set
11488:{\displaystyle w(i)\geq W/2}
10848:the tallest item height in
10181:{\displaystyle x_{r}<W/2}
7538:{\displaystyle W(m+1)/(m+2)}
7300:contains all the items with
6908:The split-fit algorithm (SF)
6338:{\displaystyle w(i)\leq W/m}
5084:{\displaystyle \delta >0}
4968:{\displaystyle \delta >0}
4082:{\displaystyle 1.9396OPT(I)}
25:according to Wäscher et al.
7:
16298:Operations Research Letters
16251:Operations Research Letters
15975:10.1007/978-3-540-77918-6_6
15520:10.1287/moor.25.4.645.12118
15267:10.1287/ijoc.15.3.310.16082
15172:Theory of Computing Systems
14748:{\displaystyle \approx 1.7}
13413:, and there exists an item
6659:are squares, it holds that
863:
816:
10:
16416:
16362:10.1016/j.ejor.2015.10.012
15702:10.4230/LIPIcs.ESA.2019.62
15194:10.1007/s00224-019-09910-6
15036:10.1016/j.ejor.2005.12.047
14910:Brown, Baker, and Katseff
10716:Steinberg's algorithm (ST)
10586:, since there are at most
7989:, there is a set of items
6006:, since there are at most
1564:the first index such that
1557:{\displaystyle i(l)\leq k}
16326:10.1016/j.tcs.2012.04.017
16263:10.1016/j.orl.2007.06.001
16205:10.1007/s10951-006-8497-6
16012:10.1007/s10878-007-9125-x
15890:SIAM Journal on Computing
15736:SIAM Journal on Computing
15651:10.1016/j.ipl.2011.10.003
15624:10.1142/S1793830911001413
15411:SIAM Journal on Computing
15309:10.1137/S0097539793255801
15297:SIAM Journal on Computing
15234:10.1016/j.tcs.2016.11.034
11346:{\displaystyle W\times H}
9810:{\displaystyle h_{\max }}
8756:{\displaystyle h_{\max }}
8134:For a given set of items
6198:{\displaystyle h_{\max }}
5759:{\displaystyle h_{\max }}
3636:
3591:
3324:
3233:
16108:10.1007/3-540-48224-5_20
12805:such that when defining
8972:Removes widest item from
8792:The split algorithm (SP)
8300:Draw a vertical line at
7487:with the FFDH algorithm.
7444:by nonincreasing height.
6756:. Furthermore, for each
6482:. Furthermore, for each
3055:approximation algorithms
566:is a point from the set
14842:{\displaystyle 1.58889}
13949:{\displaystyle \log(W)}
13777:For every set of items
13217:{\displaystyle W-W_{1}}
11919:{\displaystyle H-h_{0}}
11886:{\displaystyle W-w_{0}}
11772:{\displaystyle H-h_{0}}
11359:: It can be applied if
10623:For every set of items
9701:, it works as follows:
8602:For every set of items
8178:, it works as follows:
7685:For every set of items
7601:{\displaystyle W/(m+2)}
7169:contains all the items
6956:, it works as follows:
6258:. For any set of items
6251:{\displaystyle m\geq 2}
6043:For every set of items
5604:For every set of items
3919:{\displaystyle 2OPT(I)}
3870:{\displaystyle 2OPT(I)}
3628:{\displaystyle 3OPT(I)}
3220:{\displaystyle 3OPT(I)}
3176:Approximation guarantee
933:. Furthermore, unless
874:approximation algorithm
831:irregular strip packing
15122:Computational Geometry
14978:
14977:{\displaystyle 1.5404}
14900:
14843:
14786:
14749:
14698:
14653:
14557:
14515:
14495:
14494:{\displaystyle OPT(I)}
14460:
14428:
14332:
14283:
14231:
14182:
14133:
14069:
14040:
14012:
13950:
13917:
13896:
13859:
13795:
13768:
13631:
13611:
13610:{\displaystyle W-w(i)}
13573:
13549:
13525:
13437:
13407:
13353:
13289:
13250:
13218:
13185:
13165:
13138:
13115:
13020:
12964:
12848:
12828:
12799:
12779:
12739:
12685:
12624:
12597:
12577:
12507:
12483:
12458:
12434:
12258:
12210:
12167:
12119:
12076:
12035:
11981:
11920:
11887:
11854:
11827:
11793:
11773:
11740:
11713:
11679:
11648:
11624:
11576:
11549:be their total height.
11543:
11513:
11489:
11446:
11412:
11347:
11318:
11264:
11115:
11069:
11021:
10930:
10906:
10866:
10842:
10802:
10778:
10758:
10738:
10705:
10641:
10614:
10580:
10518:
10492:
10472:
10447:
10424:
10377:
10352:
10329:
10282:
10255:
10230:
10204:
10182:
10136:
10074:
10054:
10034:
10014:
9994:
9964:
9928:
9875:
9841:
9811:
9781:
9754:
9727:
9695:
9675:
9648:
9602:
9556:
9517:
9435:
9411:
9410:{\displaystyle C>0}
9385:
9356:
9280:
9256:
9227:
9122:
9095:
9061:
8959:A packing of the items
8891:
8871:
8851:
8831:
8811:
8781:
8757:
8730:
8620:
8593:
8546:
8461:
8434:
8407:
8379:
8352:
8322:
8291:
8258:
8231:
8204:
8172:
8152:
8119:
8007:
7983:
7955:
7861:
7835:
7723:
7709:and the corresponding
7703:
7671:
7651:
7602:
7562:
7539:
7481:
7438:
7392:
7349:
7294:
7248:
7193:
7163:
7123:
7077:
7037:
7010:
6982:
6950:
6930:
6894:
6800:
6776:
6750:
6653:
6626:
6526:
6502:
6476:
6369:
6339:
6296:
6276:
6252:
6223:
6199:
6172:
6061:
6034:
6000:
5927:
5837:
5813:
5784:
5760:
5733:
5622:
5595:
5548:
5465:
5433:
5409:
5389:
5309:
5233:
5213:
5172:
5105:
5091:, there exists a list
5085:
5056:
4989:
4975:, there exists a list
4969:
4940:
4876:
4812:
4792:
4791:{\displaystyle OPT(L)}
4757:
4725:
4664:
4644:
4643:{\displaystyle M>0}
4611:
4579:
4559:
4558:{\displaystyle r\in L}
4533:
4513:
4489:
4420:
4293:
4166:
4083:
4034:
3920:
3871:
3821:
3725:
3629:
3579:
3479:
3410:
3317:
3221:
3155:
3115:
3095:
3075:
3039:
2985:
2838:
2818:
2798:
2774:
2732:
2684:
2569:
2541:
2487:
2155:
2056:
1951:
1860:
1803:
1777:
1638:
1615:
1558:
1523:
1522:{\displaystyle l>k}
1497:
1471:
1420:
1369:
1294:
1200:
1147:. Then it holds that
1141:
1051:
1023:
988:
964:pseudo-polynomial time
956:
927:
898:
807:pseudo-polynomial time
796:
729:
560:
530:
421:
391:
338:
285:
255:
231:
201:
151:
123:
83:
54:
23:Open Dimension Problem
16390:Mathematical analysis
16193:Journal of Scheduling
15584:Discrete Optimization
15438:Journal of Algorithms
14979:
14901:
14844:
14794:Csirik and Woeginger
14787:
14750:
14699:
14654:
14558:
14516:
14496:
14461:
14429:
14333:
14284:
14232:
14183:
14134:
14070:
14041:
14013:
13951:
13918:
13897:
13860:
13796:
13769:
13632:
13612:
13574:
13550:
13526:
13438:
13408:
13354:
13290:
13251:
13219:
13186:
13166:
13164:{\displaystyle W_{1}}
13139:
13116:
13021:
12965:
12854:items it holds that
12849:
12829:
12800:
12780:
12740:
12686:
12625:
12598:
12578:
12508:
12489:and remove them from
12484:
12459:
12435:
12259:
12211:
12168:
12120:
12077:
12036:
11982:
11921:
11888:
11855:
11853:{\displaystyle w_{0}}
11828:
11794:
11774:
11746:, i.e. it has height
11741:
11739:{\displaystyle h_{0}}
11714:
11680:
11649:
11625:
11577:
11544:
11542:{\displaystyle h_{0}}
11514:
11495:and remove them from
11490:
11447:
11413:
11348:
11319:
11265:
11116:
11070:
11022:
10931:
10907:
10867:
10843:
10803:
10779:
10759:
10739:
10706:
10642:
10615:
10581:
10519:
10493:
10473:
10448:
10425:
10378:
10353:
10330:
10283:
10281:{\displaystyle h_{2}}
10256:
10231:
10205:
10183:
10137:
10075:
10055:
10035:
10015:
9995:
9993:{\displaystyle H_{1}}
9965:
9929:
9876:
9874:{\displaystyle h_{1}}
9842:
9840:{\displaystyle H_{0}}
9812:
9782:
9780:{\displaystyle H_{0}}
9755:
9753:{\displaystyle H_{0}}
9728:
9696:
9681:and a strip of width
9676:
9657:Given a set of items
9649:
9603:
9557:
9518:
9436:
9412:
9386:
9357:
9281:
9257:
9228:
9123:
9104:For any set of items
9096:
9062:
8950:, width of the strip
8938:Split Algorithm (SP)
8892:
8872:
8852:
8832:
8812:
8782:
8758:
8731:
8621:
8594:
8547:
8462:
8460:{\displaystyle h_{r}}
8435:
8433:{\displaystyle h_{l}}
8408:
8380:
8378:{\displaystyle h_{r}}
8353:
8351:{\displaystyle h_{l}}
8323:
8292:
8290:{\displaystyle h_{0}}
8259:
8257:{\displaystyle h_{0}}
8232:
8230:{\displaystyle h_{0}}
8205:
8173:
8158:and strip with width
8153:
8120:
8008:
7984:
7956:
7862:
7836:
7724:
7704:
7672:
7652:
7603:
7563:
7540:
7482:
7439:
7393:
7350:
7295:
7249:
7194:
7164:
7124:
7078:
7038:
7011:
6983:
6951:
6936:and strip with width
6931:
6895:
6801:
6777:
6751:
6654:
6627:
6527:
6503:
6477:
6370:
6340:
6297:
6282:and strip with width
6277:
6253:
6224:
6200:
6173:
6062:
6035:
6001:
5928:
5838:
5814:
5785:
5761:
5734:
5623:
5596:
5549:
5466:
5464:{\displaystyle (0,0)}
5434:
5407:
5390:
5310:
5234:
5214:
5173:
5106:
5086:
5057:
4990:
4970:
4941:
4877:
4813:
4793:
4758:
4756:{\displaystyle BL(L)}
4726:
4665:
4645:
4612:
4610:{\displaystyle (x,y)}
4580:
4560:
4534:
4511:
4490:
4421:
4294:
4167:
4084:
4035:
3921:
3872:
3822:
3726:
3630:
3595:Split Algorithm (SP)
3580:
3480:
3411:
3318:
3222:
3156:
3116:
3096:
3076:
3040:
2986:
2839:
2819:
2799:
2775:
2733:
2685:
2570:
2542:
2488:
2161:. Then it holds that
2156:
2057:
1952:
1861:
1804:
1748:
1644:. Then it holds that
1639:
1586:
1559:
1524:
1498:
1451:
1421:
1370:
1295:
1201:
1142:
1052:
1024:
989:
957:
928:
899:
797:
730:
561:
531:
422:
392:
339:
286:
256:
232:
209:strip packing problem
202:
152:
124:
84:
55:
18:strip packing problem
15470:Algorithms — ESA '94
14968:
14890:
14851:Han et al. + Seiden
14833:
14770:
14736:
14666:
14569:
14525:
14505:
14470:
14459:{\displaystyle A(I)}
14441:
14368:
14302:
14253:
14201:
14152:
14103:
14068:{\displaystyle P=NP}
14050:
14022:
13964:
13928:
13907:
13878:
13805:
13781:
13649:
13621:
13586:
13559:
13539:
13447:
13417:
13363:
13309:
13295:into the second one.
13260:
13231:
13195:
13175:
13148:
13128:
13033:
12974:
12858:
12838:
12809:
12789:
12749:
12695:
12641:
12610:
12587:
12523:
12493:
12468:
12448:
12268:
12220:
12177:
12129:
12086:
12045:
11991:
11937:
11897:
11864:
11837:
11806:
11783:
11750:
11723:
11692:
11658:
11634:
11586:
11556:
11526:
11499:
11456:
11426:
11363:
11331:
11274:
11125:
11079:
11033:
10940:
10916:
10876:
10852:
10812:
10788:
10768:
10748:
10724:
10651:
10627:
10590:
10536:
10508:
10482:
10457:
10437:
10392:
10362:
10342:
10297:
10265:
10240:
10215:
10194:
10151:
10084:
10064:
10044:
10024:
10004:
9977:
9946:
9936:second reverse-level
9885:
9858:
9824:
9794:
9764:
9737:
9709:
9685:
9661:
9612:
9566:
9536:
9445:
9421:
9395:
9369:
9290:
9266:
9240:
9132:
9108:
9071:
9017:
8881:
8861:
8841:
8821:
8801:
8767:
8740:
8630:
8606:
8556:
8480:
8444:
8417:
8389:
8362:
8335:
8304:
8274:
8241:
8214:
8186:
8162:
8138:
8017:
7993:
7967:
7871:
7845:
7733:
7713:
7689:
7661:
7615:
7572:
7552:
7494:
7451:
7402:
7362:
7304:
7258:
7203:
7173:
7133:
7087:
7047:
7023:
6992:
6964:
6940:
6916:
6810:
6786:
6760:
6663:
6639:
6635:If all the items in
6536:
6512:
6486:
6379:
6349:
6306:
6286:
6262:
6236:
6209:
6182:
6071:
6047:
6010:
5956:
5847:
5823:
5797:
5770:
5743:
5632:
5608:
5558:
5482:
5443:
5419:
5323:
5243:
5223:
5185:
5115:
5095:
5069:
4999:
4979:
4953:
4889:
4825:
4802:
4767:
4735:
4674:
4654:
4650:there exists a list
4628:
4589:
4569:
4543:
4523:
4441:
4314:
4187:
4104:
4055:
3941:
3892:
3843:
3744:
3648:
3601:
3497:
3426:
3336:
3243:
3193:
3125:
3105:
3085:
3065:
3059:heuristic approaches
2995:
2850:
2828:
2808:
2784:
2742:
2696:
2584:
2551:
2497:
2167:
2066:
1961:
1870:
1816:
1650:
1568:
1533:
1507:
1430:
1382:
1306:
1213:
1153:
1073:
1033:
1005:
996:strongly NP-complete
970:
962:, there cannot be a
955:{\displaystyle P=NP}
937:
926:{\displaystyle P=NP}
908:
880:
739:
570:
540:
431:
401:
348:
295:
265:
241:
215:
169:
133:
93:
82:{\displaystyle P=NP}
64:
36:
15551:2009LNCS.5687..177H
14863:
14820:Ye, Han, and Zhang
14709:
14086:Approximation Ratio
14079:
14039:{\displaystyle 5/4}
13895:{\displaystyle 3/2}
11630:. Remove them from
11552:Find all the items
11422:Find all the items
9963:{\displaystyle W/2}
9726:{\displaystyle W/2}
8970:i := I.pop();
8406:{\displaystyle W/2}
8321:{\displaystyle W/2}
8203:{\displaystyle W/2}
8130:Sleator's algorithm
7860:{\displaystyle m=1}
7009:{\displaystyle W/m}
5945:any previous ones.
3166:
1300:then it holds that
1050:{\displaystyle 5/4}
1022:{\displaystyle 3/2}
999:3-partition problem
987:{\displaystyle 5/4}
897:{\displaystyle 3/2}
870:bin packing problem
230:{\displaystyle W=1}
150:{\displaystyle 3/2}
53:{\displaystyle 3/2}
16213:20.500.11850/36804
16145:10.1007/BF00264439
15478:10.1007/bfb0049416
15375:Inf. Process. Lett
15002:Yu, Mao, and Xiao
14986:Balogh and Békési
14974:
14939:Hurink and Paulus
14896:
14861:
14839:
14807:Hurink and Paulus
14782:
14757:Baker and Schwarz
14745:
14707:
14694:
14649:
14553:
14511:
14491:
14456:
14424:
14328:
14279:
14227:
14178:
14129:
14077:
14065:
14036:
14008:
13946:
13913:
13892:
13855:
13791:
13764:
13627:
13607:
13569:
13545:
13521:
13433:
13403:
13349:
13285:
13246:
13214:
13181:
13161:
13134:
13111:
13016:
12960:
12844:
12824:
12795:
12775:
12735:
12681:
12620:
12593:
12573:
12503:
12482:{\displaystyle i'}
12479:
12454:
12430:
12254:
12206:
12163:
12115:
12072:
12031:
11977:
11916:
11883:
11850:
11823:
11789:
11769:
11736:
11709:
11675:
11644:
11620:
11572:
11539:
11509:
11485:
11442:
11408:
11343:
11314:
11260:
11111:
11065:
11017:
10992:
10926:
10902:
10862:
10838:
10798:
10774:
10754:
10734:
10701:
10637:
10610:
10576:
10514:
10488:
10471:{\displaystyle s'}
10468:
10443:
10420:
10376:{\displaystyle s'}
10373:
10348:
10325:
10278:
10254:{\displaystyle s'}
10251:
10229:{\displaystyle f'}
10226:
10200:
10178:
10132:
10070:
10050:
10030:
10010:
9990:
9960:
9924:
9871:
9837:
9807:
9777:
9750:
9723:
9691:
9671:
9644:
9598:
9552:
9513:
9431:
9407:
9381:
9352:
9276:
9252:
9223:
9118:
9091:
9057:
8887:
8867:
8847:
8827:
8807:
8777:
8753:
8726:
8616:
8589:
8542:
8457:
8430:
8403:
8375:
8348:
8318:
8287:
8254:
8227:
8200:
8168:
8148:
8115:
8003:
7979:
7951:
7857:
7831:
7719:
7699:
7667:
7647:
7598:
7558:
7535:
7477:
7447:Pack the items in
7434:
7388:
7345:
7290:
7244:
7189:
7159:
7119:
7073:
7033:
7006:
6978:
6946:
6926:
6890:
6796:
6772:
6746:
6649:
6622:
6522:
6498:
6472:
6365:
6335:
6292:
6272:
6248:
6219:
6195:
6168:
6057:
6030:
5996:
5923:
5833:
5809:
5780:
5756:
5729:
5618:
5591:
5544:
5461:
5429:
5410:
5385:
5305:
5229:
5209:
5168:
5101:
5081:
5052:
4985:
4965:
4936:
4872:
4808:
4788:
4753:
4721:
4660:
4640:
4607:
4575:
4555:
4529:
4514:
4485:
4416:
4289:
4174:Jansen, Solis-Oba
4162:
4079:
4030:
3916:
3867:
3817:
3721:
3625:
3575:
3475:
3406:
3313:
3217:
3164:
3151:
3111:
3091:
3071:
3035:
2981:
2834:
2814:
2794:
2770:
2728:
2680:
2565:
2537:
2483:
2460:
2422:
2303:
2234:
2151:
2052:
1947:
1856:
1799:
1634:
1554:
1519:
1493:
1416:
1365:
1290:
1265:
1196:
1137:
1047:
1019:
984:
952:
923:
894:
858:guillotine packing
792:
725:
556:
526:
417:
387:
334:
281:
251:
227:
197:
147:
119:
79:
50:
16319:. 440–441: 1–13.
16117:978-3-540-42287-7
16073:978-3-540-72868-9
15984:978-3-540-77917-9
15866:978-3-319-53924-9
15780:978-1-61197-433-1
15748:10.1137/080736491
15568:978-3-642-03684-2
15487:978-3-540-58434-6
15006:
15005:
14955:Kern and Paulus
14899:{\displaystyle 2}
14870:Competitive Ratio
14855:
14854:
14716:Competitive Ratio
14563:it is defined as
14514:{\displaystyle I}
14350:Online algorithms
14347:
14346:
14190:Nadiradze, Wiese
13916:{\displaystyle W}
13630:{\displaystyle H}
13548:{\displaystyle i}
13184:{\displaystyle H}
13137:{\displaystyle H}
12847:{\displaystyle m}
12798:{\displaystyle m}
12596:{\displaystyle H}
12457:{\displaystyle i}
11792:{\displaystyle W}
10973:
10777:{\displaystyle H}
10757:{\displaystyle W}
10517:{\displaystyle s}
10491:{\displaystyle s}
10446:{\displaystyle s}
10351:{\displaystyle s}
10203:{\displaystyle s}
10073:{\displaystyle s}
10053:{\displaystyle f}
10033:{\displaystyle s}
10013:{\displaystyle f}
9694:{\displaystyle W}
8890:{\displaystyle i}
8870:{\displaystyle i}
8850:{\displaystyle j}
8830:{\displaystyle j}
8810:{\displaystyle i}
8171:{\displaystyle W}
7722:{\displaystyle m}
7670:{\displaystyle R}
7561:{\displaystyle R}
6949:{\displaystyle W}
6295:{\displaystyle W}
5383:
5303:
5232:{\displaystyle L}
5104:{\displaystyle L}
4988:{\displaystyle L}
4811:{\displaystyle L}
4663:{\displaystyle L}
4578:{\displaystyle r}
4532:{\displaystyle L}
4501:
4500:
4091:Harren, van Stee
3796:
3700:
3642:Mixed Algoritghm
3114:{\displaystyle 2}
3094:{\displaystyle 2}
3074:{\displaystyle 3}
2837:{\displaystyle H}
2817:{\displaystyle W}
2464:
2387:
2326:
2242:
2191:
1246:
16407:
16395:Packing problems
16374:
16373:
16345:
16339:
16338:
16328:
16308:
16302:
16301:
16289:
16283:
16282:
16248:
16239:
16233:
16232:
16190:
16181:
16175:
16174:
16156:
16133:Acta Informatica
16128:
16122:
16121:
16095:
16086:
16085:
16057:
16041:
16032:
16031:
15995:
15989:
15988:
15964:
15955:
15949:
15948:
15920:
15914:
15913:
15885:
15879:
15878:
15850:
15834:
15828:
15827:
15807:
15791:
15785:
15784:
15758:
15752:
15751:
15742:(8): 3571–3615.
15731:
15725:
15724:
15704:
15688:
15679:
15678:
15677:
15661:
15655:
15654:
15634:
15628:
15627:
15606:
15600:
15599:
15579:
15573:
15572:
15538:
15532:
15531:
15498:
15492:
15491:
15465:
15454:
15453:
15433:
15427:
15426:
15406:
15391:
15390:
15370:
15361:
15360:
15340:
15313:
15312:
15292:
15279:
15278:
15250:
15239:
15238:
15236:
15212:
15206:
15205:
15187:
15167:
15158:
15157:
15155:
15146:
15140:
15139:
15137:
15113:
15104:
15103:
15093:
15073:
15048:
15047:
15030:(3): 1109–1130.
15019:
14983:
14981:
14980:
14975:
14905:
14903:
14902:
14897:
14864:
14860:
14848:
14846:
14845:
14840:
14791:
14789:
14788:
14783:
14754:
14752:
14751:
14746:
14710:
14706:
14703:
14701:
14700:
14695:
14678:
14677:
14658:
14656:
14655:
14650:
14630:
14613:
14612:
14586:
14562:
14560:
14559:
14554:
14537:
14536:
14520:
14518:
14517:
14512:
14500:
14498:
14497:
14492:
14465:
14463:
14462:
14457:
14433:
14431:
14430:
14425:
14405:
14388:
14387:
14382:
14337:
14335:
14334:
14329:
14315:
14288:
14286:
14285:
14280:
14266:
14236:
14234:
14233:
14228:
14214:
14187:
14185:
14184:
14179:
14165:
14138:
14136:
14135:
14130:
14116:
14080:
14076:
14074:
14072:
14071:
14066:
14045:
14043:
14042:
14037:
14032:
14017:
14015:
14014:
14009:
13977:
13955:
13953:
13952:
13947:
13922:
13920:
13919:
13914:
13901:
13899:
13898:
13893:
13888:
13864:
13862:
13861:
13856:
13851:
13850:
13823:
13822:
13800:
13798:
13797:
13792:
13790:
13789:
13773:
13771:
13770:
13765:
13754:
13749:
13748:
13742:
13719:
13714:
13713:
13704:
13699:
13698:
13692:
13678:
13673:
13672:
13666:
13658:
13657:
13636:
13634:
13633:
13628:
13616:
13614:
13613:
13608:
13578:
13576:
13575:
13570:
13568:
13567:
13554:
13552:
13551:
13546:
13530:
13528:
13527:
13522:
13517:
13500:
13499:
13490:
13442:
13440:
13439:
13434:
13432:
13431:
13412:
13410:
13409:
13404:
13399:
13385:
13384:
13375:
13374:
13358:
13356:
13355:
13350:
13345:
13331:
13330:
13321:
13320:
13294:
13292:
13291:
13286:
13284:
13283:
13282:
13269:
13268:
13255:
13253:
13252:
13247:
13245:
13244:
13243:
13223:
13221:
13220:
13215:
13213:
13212:
13190:
13188:
13187:
13182:
13170:
13168:
13167:
13162:
13160:
13159:
13143:
13141:
13140:
13135:
13120:
13118:
13117:
13112:
13110:
13106:
13098:
13097:
13096:
13083:
13060:
13045:
13044:
13025:
13023:
13022:
13017:
13012:
12998:
12997:
12969:
12967:
12966:
12961:
12956:
12936:
12935:
12934:
12921:
12901:
12884:
12883:
12874:
12853:
12851:
12850:
12845:
12833:
12831:
12830:
12825:
12823:
12822:
12821:
12804:
12802:
12801:
12796:
12784:
12782:
12781:
12776:
12768:
12763:
12762:
12756:
12744:
12742:
12741:
12736:
12731:
12717:
12716:
12707:
12706:
12690:
12688:
12687:
12682:
12677:
12663:
12662:
12653:
12652:
12629:
12627:
12626:
12621:
12619:
12618:
12602:
12600:
12599:
12594:
12582:
12580:
12579:
12574:
12566:
12512:
12510:
12509:
12504:
12502:
12501:
12488:
12486:
12485:
12480:
12478:
12463:
12461:
12460:
12455:
12439:
12437:
12436:
12431:
12417:
12364:
12347:
12300:
12299:
12290:
12263:
12261:
12260:
12255:
12250:
12236:
12215:
12213:
12212:
12207:
12202:
12172:
12170:
12169:
12164:
12159:
12145:
12124:
12122:
12121:
12116:
12111:
12081:
12079:
12078:
12073:
12071:
12070:
12061:
12040:
12038:
12037:
12032:
12027:
12013:
12012:
12003:
12002:
11986:
11984:
11983:
11978:
11973:
11959:
11958:
11949:
11948:
11925:
11923:
11922:
11917:
11915:
11914:
11892:
11890:
11889:
11884:
11882:
11881:
11859:
11857:
11856:
11851:
11849:
11848:
11832:
11830:
11829:
11824:
11822:
11821:
11816:
11815:
11798:
11796:
11795:
11790:
11778:
11776:
11775:
11770:
11768:
11767:
11745:
11743:
11742:
11737:
11735:
11734:
11718:
11716:
11715:
11710:
11708:
11707:
11702:
11701:
11684:
11682:
11681:
11676:
11674:
11673:
11668:
11667:
11653:
11651:
11650:
11645:
11643:
11642:
11629:
11627:
11626:
11621:
11619:
11618:
11581:
11579:
11578:
11573:
11571:
11570:
11548:
11546:
11545:
11540:
11538:
11537:
11518:
11516:
11515:
11510:
11508:
11507:
11494:
11492:
11491:
11486:
11481:
11451:
11449:
11448:
11443:
11441:
11440:
11417:
11415:
11414:
11409:
11404:
11390:
11386:
11385:
11375:
11374:
11352:
11350:
11349:
11344:
11323:
11321:
11320:
11315:
11292:
11291:
11269:
11267:
11266:
11261:
11259:
11258:
11240:
11239:
11230:
11229:
11214:
11213:
11195:
11194:
11185:
11184:
11151:
11150:
11141:
11120:
11118:
11117:
11112:
11101:
11100:
11091:
11090:
11074:
11072:
11071:
11066:
11055:
11054:
11045:
11044:
11026:
11024:
11023:
11018:
10991:
10990:
10989:
10966:
10965:
10956:
10935:
10933:
10932:
10927:
10925:
10924:
10911:
10909:
10908:
10903:
10898:
10897:
10888:
10887:
10871:
10869:
10868:
10863:
10861:
10860:
10847:
10845:
10844:
10839:
10834:
10833:
10824:
10823:
10807:
10805:
10804:
10799:
10797:
10796:
10783:
10781:
10780:
10775:
10763:
10761:
10760:
10755:
10743:
10741:
10740:
10735:
10733:
10732:
10710:
10708:
10707:
10702:
10697:
10696:
10669:
10668:
10646:
10644:
10643:
10638:
10636:
10635:
10619:
10617:
10616:
10611:
10609:
10604:
10603:
10597:
10585:
10583:
10582:
10577:
10572:
10571:
10566:
10560:
10559:
10553:
10545:
10544:
10523:
10521:
10520:
10515:
10497:
10495:
10494:
10489:
10477:
10475:
10474:
10469:
10467:
10452:
10450:
10449:
10444:
10429:
10427:
10426:
10421:
10404:
10403:
10382:
10380:
10379:
10374:
10372:
10357:
10355:
10354:
10349:
10334:
10332:
10331:
10326:
10309:
10308:
10287:
10285:
10284:
10279:
10277:
10276:
10260:
10258:
10257:
10252:
10250:
10235:
10233:
10232:
10227:
10225:
10209:
10207:
10206:
10201:
10187:
10185:
10184:
10179:
10174:
10163:
10162:
10141:
10139:
10138:
10133:
10128:
10127:
10115:
10114:
10096:
10095:
10079:
10077:
10076:
10071:
10059:
10057:
10056:
10051:
10039:
10037:
10036:
10031:
10019:
10017:
10016:
10011:
9999:
9997:
9996:
9991:
9989:
9988:
9969:
9967:
9966:
9961:
9956:
9933:
9931:
9930:
9925:
9923:
9922:
9910:
9909:
9897:
9896:
9880:
9878:
9877:
9872:
9870:
9869:
9846:
9844:
9843:
9838:
9836:
9835:
9816:
9814:
9813:
9808:
9806:
9805:
9786:
9784:
9783:
9778:
9776:
9775:
9759:
9757:
9756:
9751:
9749:
9748:
9732:
9730:
9729:
9724:
9719:
9700:
9698:
9697:
9692:
9680:
9678:
9677:
9672:
9670:
9669:
9653:
9651:
9650:
9645:
9640:
9639:
9627:
9626:
9607:
9605:
9604:
9599:
9594:
9593:
9581:
9580:
9561:
9559:
9558:
9553:
9551:
9550:
9528:Reverse-fit (RF)
9522:
9520:
9519:
9514:
9503:
9502:
9463:
9462:
9440:
9438:
9437:
9432:
9430:
9429:
9416:
9414:
9413:
9408:
9390:
9388:
9387:
9382:
9361:
9359:
9358:
9353:
9348:
9347:
9308:
9307:
9285:
9283:
9282:
9277:
9275:
9274:
9261:
9259:
9258:
9253:
9232:
9230:
9229:
9224:
9219:
9218:
9194:
9193:
9178:
9177:
9150:
9149:
9127:
9125:
9124:
9119:
9117:
9116:
9100:
9098:
9097:
9092:
9090:
9085:
9084:
9078:
9066:
9064:
9063:
9058:
9053:
9052:
9047:
9041:
9040:
9034:
9026:
9025:
8953:
8949:
8931:
8927:
8923:
8919:
8915:
8911:
8907:
8903:
8896:
8894:
8893:
8888:
8876:
8874:
8873:
8868:
8856:
8854:
8853:
8848:
8836:
8834:
8833:
8828:
8816:
8814:
8813:
8808:
8786:
8784:
8783:
8778:
8776:
8775:
8762:
8760:
8759:
8754:
8752:
8751:
8735:
8733:
8732:
8727:
8722:
8721:
8694:
8689:
8688:
8673:
8672:
8645:
8644:
8625:
8623:
8622:
8617:
8615:
8614:
8598:
8596:
8595:
8590:
8585:
8580:
8579:
8573:
8565:
8564:
8551:
8549:
8548:
8543:
8535:
8530:
8529:
8523:
8509:
8504:
8503:
8497:
8489:
8488:
8466:
8464:
8463:
8458:
8456:
8455:
8439:
8437:
8436:
8431:
8429:
8428:
8412:
8410:
8409:
8404:
8399:
8384:
8382:
8381:
8376:
8374:
8373:
8357:
8355:
8354:
8349:
8347:
8346:
8327:
8325:
8324:
8319:
8314:
8296:
8294:
8293:
8288:
8286:
8285:
8263:
8261:
8260:
8255:
8253:
8252:
8236:
8234:
8233:
8228:
8226:
8225:
8209:
8207:
8206:
8201:
8196:
8177:
8175:
8174:
8169:
8157:
8155:
8154:
8149:
8147:
8146:
8124:
8122:
8121:
8116:
8111:
8110:
8092:
8088:
8066:
8035:
8034:
8012:
8010:
8009:
8004:
8002:
8001:
7988:
7986:
7985:
7980:
7960:
7958:
7957:
7952:
7950:
7949:
7931:
7930:
7906:
7889:
7888:
7867:, it holds that
7866:
7864:
7863:
7858:
7841:. Note that for
7840:
7838:
7837:
7832:
7830:
7829:
7811:
7810:
7777:
7751:
7750:
7729:, it holds that
7728:
7726:
7725:
7720:
7708:
7706:
7705:
7700:
7698:
7697:
7676:
7674:
7673:
7668:
7656:
7654:
7653:
7648:
7646:
7645:
7625:
7624:
7607:
7605:
7604:
7599:
7582:
7567:
7565:
7564:
7559:
7544:
7542:
7541:
7536:
7519:
7486:
7484:
7483:
7478:
7476:
7475:
7461:
7460:
7443:
7441:
7440:
7435:
7433:
7432:
7412:
7411:
7397:
7395:
7394:
7389:
7387:
7386:
7372:
7371:
7354:
7352:
7351:
7346:
7329:
7299:
7297:
7296:
7291:
7289:
7288:
7268:
7267:
7253:
7251:
7250:
7245:
7228:
7198:
7196:
7195:
7190:
7188:
7187:
7168:
7166:
7165:
7160:
7158:
7157:
7143:
7142:
7128:
7126:
7125:
7120:
7118:
7117:
7097:
7096:
7082:
7080:
7079:
7074:
7072:
7071:
7057:
7056:
7042:
7040:
7039:
7034:
7032:
7031:
7015:
7013:
7012:
7007:
7002:
6987:
6985:
6984:
6979:
6977:
6955:
6953:
6952:
6947:
6935:
6933:
6932:
6927:
6925:
6924:
6899:
6897:
6896:
6891:
6886:
6885:
6867:
6863:
6853:
6834:
6833:
6805:
6803:
6802:
6797:
6795:
6794:
6781:
6779:
6778:
6773:
6755:
6753:
6752:
6747:
6745:
6744:
6729:
6728:
6704:
6687:
6686:
6658:
6656:
6655:
6650:
6648:
6647:
6631:
6629:
6628:
6623:
6618:
6617:
6599:
6595:
6585:
6560:
6559:
6531:
6529:
6528:
6523:
6521:
6520:
6507:
6505:
6504:
6499:
6481:
6479:
6478:
6473:
6471:
6470:
6455:
6454:
6436:
6432:
6428:
6403:
6402:
6375:, it holds that
6374:
6372:
6371:
6366:
6364:
6363:
6344:
6342:
6341:
6336:
6331:
6301:
6299:
6298:
6293:
6281:
6279:
6278:
6273:
6271:
6270:
6257:
6255:
6254:
6249:
6228:
6226:
6225:
6220:
6218:
6217:
6204:
6202:
6201:
6196:
6194:
6193:
6177:
6175:
6174:
6169:
6164:
6163:
6139:
6138:
6123:
6122:
6095:
6094:
6066:
6064:
6063:
6058:
6056:
6055:
6039:
6037:
6036:
6031:
6029:
6024:
6023:
6017:
6005:
6003:
6002:
5997:
5992:
5991:
5986:
5980:
5979:
5973:
5965:
5964:
5932:
5930:
5929:
5924:
5916:
5915:
5876:
5871:
5870:
5842:
5840:
5839:
5834:
5832:
5831:
5818:
5816:
5815:
5810:
5789:
5787:
5786:
5781:
5779:
5778:
5765:
5763:
5762:
5757:
5755:
5754:
5738:
5736:
5735:
5730:
5725:
5724:
5700:
5699:
5684:
5683:
5656:
5655:
5627:
5625:
5624:
5619:
5617:
5616:
5600:
5598:
5597:
5592:
5587:
5582:
5581:
5575:
5567:
5566:
5553:
5551:
5550:
5545:
5537:
5532:
5531:
5525:
5511:
5506:
5505:
5499:
5491:
5490:
5470:
5468:
5467:
5462:
5438:
5436:
5435:
5430:
5428:
5427:
5394:
5392:
5391:
5386:
5384:
5382:
5368:
5345:
5314:
5312:
5311:
5306:
5304:
5302:
5288:
5265:
5238:
5236:
5235:
5230:
5218:
5216:
5215:
5210:
5177:
5175:
5174:
5169:
5137:
5110:
5108:
5107:
5102:
5090:
5088:
5087:
5082:
5061:
5059:
5058:
5053:
5021:
4994:
4992:
4991:
4986:
4974:
4972:
4971:
4966:
4945:
4943:
4942:
4937:
4911:
4881:
4879:
4878:
4873:
4847:
4817:
4815:
4814:
4809:
4797:
4795:
4794:
4789:
4762:
4760:
4759:
4754:
4730:
4728:
4727:
4722:
4696:
4669:
4667:
4666:
4661:
4649:
4647:
4646:
4641:
4616:
4614:
4613:
4608:
4584:
4582:
4581:
4576:
4564:
4562:
4561:
4556:
4538:
4536:
4535:
4530:
4494:
4492:
4491:
4486:
4454:
4425:
4423:
4422:
4417:
4406:
4405:
4390:
4379:
4359:
4358:
4301:Bougeret et al.
4298:
4296:
4295:
4290:
4279:
4278:
4263:
4252:
4232:
4231:
4171:
4169:
4168:
4163:
4152:
4151:
4088:
4086:
4085:
4080:
4039:
4037:
4036:
4031:
4020:
4019:
4007:
4006:
3997:
3986:
3985:
3925:
3923:
3922:
3917:
3876:
3874:
3873:
3868:
3826:
3824:
3823:
3818:
3807:
3806:
3797:
3789:
3757:
3730:
3728:
3727:
3722:
3711:
3710:
3701:
3693:
3661:
3634:
3632:
3631:
3626:
3584:
3582:
3581:
3576:
3547:
3533:
3532:
3484:
3482:
3481:
3476:
3465:
3464:
3415:
3413:
3412:
3407:
3372:
3371:
3322:
3320:
3319:
3314:
3279:
3278:
3226:
3224:
3223:
3218:
3167:
3163:
3160:
3158:
3157:
3152:
3138:
3120:
3118:
3117:
3112:
3100:
3098:
3097:
3092:
3080:
3078:
3077:
3072:
3044:
3042:
3041:
3036:
3013:
3012:
2990:
2988:
2987:
2982:
2980:
2979:
2955:
2954:
2939:
2938:
2920:
2919:
2910:
2909:
2888:
2887:
2878:
2843:
2841:
2840:
2835:
2823:
2821:
2820:
2815:
2803:
2801:
2800:
2795:
2793:
2792:
2779:
2777:
2776:
2771:
2760:
2759:
2737:
2735:
2734:
2729:
2724:
2723:
2714:
2713:
2689:
2687:
2686:
2681:
2670:
2662:
2661:
2652:
2626:
2625:
2574:
2572:
2571:
2566:
2564:
2546:
2544:
2543:
2538:
2515:
2514:
2492:
2490:
2489:
2484:
2482:
2481:
2475:
2474:
2469:
2465:
2459:
2421:
2411:
2410:
2405:
2404:
2350:
2349:
2344:
2343:
2325:
2302:
2292:
2291:
2286:
2285:
2266:
2265:
2260:
2259:
2241:
2240:
2233:
2232:
2218:
2160:
2158:
2157:
2152:
2123:
2115:
2110:
2109:
2082:
2081:
2076:
2075:
2061:
2059:
2058:
2053:
2045:
2010:
2005:
2004:
1977:
1976:
1971:
1970:
1956:
1954:
1953:
1948:
1919:
1914:
1913:
1886:
1885:
1880:
1879:
1865:
1863:
1862:
1857:
1855:
1841:
1808:
1806:
1805:
1800:
1776:
1762:
1720:
1643:
1641:
1640:
1635:
1614:
1600:
1563:
1561:
1560:
1555:
1528:
1526:
1525:
1520:
1502:
1500:
1499:
1494:
1470:
1465:
1425:
1423:
1422:
1417:
1391:
1390:
1374:
1372:
1371:
1366:
1361:
1353:
1352:
1343:
1299:
1297:
1296:
1291:
1264:
1263:
1262:
1239:
1238:
1229:
1205:
1203:
1202:
1197:
1186:
1185:
1146:
1144:
1143:
1138:
1133:
1132:
1120:
1085:
1084:
1056:
1054:
1053:
1048:
1043:
1028:
1026:
1025:
1020:
1015:
993:
991:
990:
985:
980:
961:
959:
958:
953:
932:
930:
929:
924:
903:
901:
900:
895:
890:
801:
799:
798:
793:
788:
787:
775:
770:
769:
757:
756:
734:
732:
731:
726:
721:
720:
708:
707:
689:
688:
676:
675:
663:
662:
644:
643:
634:
629:
621:
583:
565:
563:
562:
557:
555:
554:
535:
533:
532:
527:
525:
524:
516:
504:
493:
492:
459:
458:
446:
445:
426:
424:
423:
418:
416:
415:
396:
394:
393:
388:
386:
360:
359:
343:
341:
340:
335:
333:
307:
306:
290:
288:
287:
282:
280:
279:
260:
258:
257:
252:
250:
249:
236:
234:
233:
228:
206:
204:
203:
198:
187:
186:
156:
154:
153:
148:
143:
128:
126:
125:
120:
106:
88:
86:
85:
80:
59:
57:
56:
51:
46:
16415:
16414:
16410:
16409:
16408:
16406:
16405:
16404:
16380:
16379:
16378:
16377:
16346:
16342:
16309:
16305:
16290:
16286:
16246:
16240:
16236:
16188:
16182:
16178:
16129:
16125:
16118:
16096:
16089:
16074:
16042:
16035:
15996:
15992:
15985:
15962:
15956:
15952:
15921:
15917:
15902:10.1137/0212033
15886:
15882:
15867:
15835:
15831:
15816:
15792:
15788:
15781:
15759:
15755:
15732:
15728:
15713:
15689:
15682:
15662:
15658:
15635:
15631:
15607:
15603:
15580:
15576:
15569:
15539:
15535:
15499:
15495:
15488:
15466:
15457:
15434:
15430:
15423:10.1137/0210042
15407:
15394:
15371:
15364:
15357:10.1137/0209062
15341:
15316:
15293:
15282:
15251:
15242:
15213:
15209:
15168:
15161:
15153:
15147:
15143:
15114:
15107:
15100:10.1137/0209064
15091:10.1.1.309.8883
15074:
15051:
15020:
15016:
15011:
14969:
14966:
14965:
14891:
14888:
14887:
14834:
14831:
14830:
14771:
14768:
14767:
14737:
14734:
14733:
14673:
14669:
14667:
14664:
14663:
14626:
14587:
14576:
14575:
14570:
14567:
14566:
14532:
14528:
14526:
14523:
14522:
14506:
14503:
14502:
14471:
14468:
14467:
14442:
14439:
14438:
14401:
14383:
14372:
14371:
14369:
14366:
14365:
14352:
14311:
14303:
14300:
14299:
14262:
14254:
14251:
14250:
14210:
14202:
14199:
14198:
14161:
14153:
14150:
14149:
14112:
14104:
14101:
14100:
14051:
14048:
14047:
14028:
14023:
14020:
14019:
13973:
13965:
13962:
13961:
13929:
13926:
13925:
13908:
13905:
13904:
13884:
13879:
13876:
13875:
13872:
13846:
13845:
13818:
13817:
13806:
13803:
13802:
13785:
13784:
13782:
13779:
13778:
13750:
13744:
13743:
13738:
13715:
13709:
13705:
13700:
13694:
13693:
13688:
13674:
13668:
13667:
13662:
13653:
13652:
13650:
13647:
13646:
13622:
13619:
13618:
13587:
13584:
13583:
13563:
13562:
13560:
13557:
13556:
13540:
13537:
13536:
13535:Place the item
13513:
13495:
13494:
13477:
13448:
13445:
13444:
13427:
13426:
13418:
13415:
13414:
13395:
13380:
13379:
13370:
13366:
13364:
13361:
13360:
13341:
13326:
13325:
13316:
13312:
13310:
13307:
13306:
13275:
13274:
13273:
13264:
13263:
13261:
13258:
13257:
13236:
13235:
13234:
13232:
13229:
13228:
13208:
13204:
13196:
13193:
13192:
13176:
13173:
13172:
13155:
13151:
13149:
13146:
13145:
13129:
13126:
13125:
13102:
13089:
13088:
13087:
13070:
13056:
13052:
13040:
13036:
13034:
13031:
13030:
13008:
12987:
12983:
12975:
12972:
12971:
12952:
12927:
12926:
12925:
12908:
12897:
12879:
12878:
12861:
12859:
12856:
12855:
12839:
12836:
12835:
12814:
12813:
12812:
12810:
12807:
12806:
12790:
12787:
12786:
12764:
12758:
12757:
12752:
12750:
12747:
12746:
12727:
12712:
12711:
12702:
12698:
12696:
12693:
12692:
12673:
12658:
12657:
12648:
12644:
12642:
12639:
12638:
12614:
12613:
12611:
12608:
12607:
12588:
12585:
12584:
12559:
12524:
12521:
12520:
12497:
12496:
12494:
12491:
12490:
12471:
12469:
12466:
12465:
12449:
12446:
12445:
12410:
12357:
12340:
12295:
12294:
12277:
12269:
12266:
12265:
12246:
12229:
12221:
12218:
12217:
12198:
12178:
12175:
12174:
12155:
12138:
12130:
12127:
12126:
12107:
12087:
12084:
12083:
12066:
12065:
12054:
12046:
12043:
12042:
12023:
12008:
12007:
11998:
11994:
11992:
11989:
11988:
11969:
11954:
11953:
11944:
11940:
11938:
11935:
11934:
11910:
11906:
11898:
11895:
11894:
11877:
11873:
11865:
11862:
11861:
11844:
11840:
11838:
11835:
11834:
11817:
11811:
11810:
11809:
11807:
11804:
11803:
11784:
11781:
11780:
11763:
11759:
11751:
11748:
11747:
11730:
11726:
11724:
11721:
11720:
11703:
11697:
11696:
11695:
11693:
11690:
11689:
11669:
11663:
11662:
11661:
11659:
11656:
11655:
11638:
11637:
11635:
11632:
11631:
11614:
11610:
11587:
11584:
11583:
11566:
11565:
11557:
11554:
11553:
11533:
11529:
11527:
11524:
11523:
11503:
11502:
11500:
11497:
11496:
11477:
11457:
11454:
11453:
11436:
11435:
11427:
11424:
11423:
11400:
11381:
11380:
11379:
11370:
11366:
11364:
11361:
11360:
11332:
11329:
11328:
11287:
11283:
11275:
11272:
11271:
11254:
11250:
11235:
11234:
11225:
11221:
11209:
11205:
11190:
11189:
11180:
11176:
11146:
11145:
11128:
11126:
11123:
11122:
11096:
11095:
11086:
11082:
11080:
11077:
11076:
11050:
11049:
11040:
11036:
11034:
11031:
11030:
10985:
10984:
10977:
10961:
10960:
10943:
10941:
10938:
10937:
10920:
10919:
10917:
10914:
10913:
10893:
10892:
10883:
10879:
10877:
10874:
10873:
10856:
10855:
10853:
10850:
10849:
10829:
10828:
10819:
10815:
10813:
10810:
10809:
10792:
10791:
10789:
10786:
10785:
10769:
10766:
10765:
10749:
10746:
10745:
10728:
10727:
10725:
10722:
10721:
10718:
10692:
10691:
10664:
10663:
10652:
10649:
10648:
10631:
10630:
10628:
10625:
10624:
10605:
10599:
10598:
10593:
10591:
10588:
10587:
10567:
10562:
10561:
10555:
10554:
10549:
10540:
10539:
10537:
10534:
10533:
10509:
10506:
10505:
10483:
10480:
10479:
10460:
10458:
10455:
10454:
10438:
10435:
10434:
10399:
10395:
10393:
10390:
10389:
10365:
10363:
10360:
10359:
10343:
10340:
10339:
10304:
10300:
10298:
10295:
10294:
10272:
10268:
10266:
10263:
10262:
10243:
10241:
10238:
10237:
10218:
10216:
10213:
10212:
10195:
10192:
10191:
10170:
10158:
10154:
10152:
10149:
10148:
10123:
10119:
10110:
10106:
10091:
10087:
10085:
10082:
10081:
10065:
10062:
10061:
10045:
10042:
10041:
10025:
10022:
10021:
10005:
10002:
10001:
9984:
9980:
9978:
9975:
9974:
9952:
9947:
9944:
9943:
9918:
9914:
9905:
9901:
9892:
9888:
9886:
9883:
9882:
9865:
9861:
9859:
9856:
9855:
9831:
9827:
9825:
9822:
9821:
9801:
9797:
9795:
9792:
9791:
9771:
9767:
9765:
9762:
9761:
9744:
9740:
9738:
9735:
9734:
9715:
9710:
9707:
9706:
9686:
9683:
9682:
9665:
9664:
9662:
9659:
9658:
9635:
9631:
9622:
9618:
9613:
9610:
9609:
9589:
9585:
9576:
9572:
9567:
9564:
9563:
9546:
9545:
9537:
9534:
9533:
9530:
9498:
9497:
9458:
9457:
9446:
9443:
9442:
9425:
9424:
9422:
9419:
9418:
9396:
9393:
9392:
9370:
9367:
9366:
9343:
9342:
9303:
9302:
9291:
9288:
9287:
9270:
9269:
9267:
9264:
9263:
9241:
9238:
9237:
9214:
9213:
9189:
9185:
9173:
9172:
9145:
9144:
9133:
9130:
9129:
9112:
9111:
9109:
9106:
9105:
9086:
9080:
9079:
9074:
9072:
9069:
9068:
9048:
9043:
9042:
9036:
9035:
9030:
9021:
9020:
9018:
9015:
9014:
9007:
8951:
8947:
8929:
8925:
8921:
8917:
8913:
8909:
8905:
8901:
8882:
8879:
8878:
8862:
8859:
8858:
8842:
8839:
8838:
8822:
8819:
8818:
8802:
8799:
8798:
8794:
8771:
8770:
8768:
8765:
8764:
8747:
8743:
8741:
8738:
8737:
8717:
8716:
8690:
8684:
8680:
8668:
8667:
8640:
8639:
8631:
8628:
8627:
8610:
8609:
8607:
8604:
8603:
8581:
8575:
8574:
8569:
8560:
8559:
8557:
8554:
8553:
8531:
8525:
8524:
8519:
8505:
8499:
8498:
8493:
8484:
8483:
8481:
8478:
8477:
8451:
8447:
8445:
8442:
8441:
8424:
8420:
8418:
8415:
8414:
8395:
8390:
8387:
8386:
8369:
8365:
8363:
8360:
8359:
8342:
8338:
8336:
8333:
8332:
8310:
8305:
8302:
8301:
8281:
8277:
8275:
8272:
8271:
8248:
8244:
8242:
8239:
8238:
8221:
8217:
8215:
8212:
8211:
8192:
8187:
8184:
8183:
8163:
8160:
8159:
8142:
8141:
8139:
8136:
8135:
8132:
8106:
8105:
8062:
8046:
8042:
8030:
8029:
8018:
8015:
8014:
7997:
7996:
7994:
7991:
7990:
7968:
7965:
7964:
7945:
7941:
7926:
7925:
7902:
7884:
7883:
7872:
7869:
7868:
7846:
7843:
7842:
7825:
7821:
7806:
7805:
7773:
7746:
7745:
7734:
7731:
7730:
7714:
7711:
7710:
7693:
7692:
7690:
7687:
7686:
7662:
7659:
7658:
7657:using the area
7626:
7620:
7619:
7618:
7616:
7613:
7612:
7578:
7573:
7570:
7569:
7553:
7550:
7549:
7515:
7495:
7492:
7491:
7462:
7456:
7455:
7454:
7452:
7449:
7448:
7413:
7407:
7406:
7405:
7403:
7400:
7399:
7373:
7367:
7366:
7365:
7363:
7360:
7359:
7325:
7305:
7302:
7301:
7269:
7263:
7262:
7261:
7259:
7256:
7255:
7224:
7204:
7201:
7200:
7183:
7182:
7174:
7171:
7170:
7144:
7138:
7137:
7136:
7134:
7131:
7130:
7098:
7092:
7091:
7090:
7088:
7085:
7084:
7058:
7052:
7051:
7050:
7048:
7045:
7044:
7027:
7026:
7024:
7021:
7020:
6998:
6993:
6990:
6989:
6973:
6965:
6962:
6961:
6941:
6938:
6937:
6920:
6919:
6917:
6914:
6913:
6910:
6881:
6880:
6849:
6845:
6841:
6829:
6828:
6811:
6808:
6807:
6790:
6789:
6787:
6784:
6783:
6761:
6758:
6757:
6740:
6736:
6724:
6723:
6700:
6682:
6681:
6664:
6661:
6660:
6643:
6642:
6640:
6637:
6636:
6613:
6612:
6581:
6571:
6567:
6555:
6554:
6537:
6534:
6533:
6516:
6515:
6513:
6510:
6509:
6487:
6484:
6483:
6466:
6462:
6450:
6449:
6424:
6414:
6410:
6398:
6397:
6380:
6377:
6376:
6359:
6358:
6350:
6347:
6346:
6327:
6307:
6304:
6303:
6287:
6284:
6283:
6266:
6265:
6263:
6260:
6259:
6237:
6234:
6233:
6213:
6212:
6210:
6207:
6206:
6189:
6185:
6183:
6180:
6179:
6159:
6158:
6134:
6130:
6118:
6117:
6090:
6089:
6072:
6069:
6068:
6051:
6050:
6048:
6045:
6044:
6025:
6019:
6018:
6013:
6011:
6008:
6007:
5987:
5982:
5981:
5975:
5974:
5969:
5960:
5959:
5957:
5954:
5953:
5942:
5911:
5910:
5872:
5866:
5865:
5848:
5845:
5844:
5827:
5826:
5824:
5821:
5820:
5798:
5795:
5794:
5774:
5773:
5771:
5768:
5767:
5750:
5746:
5744:
5741:
5740:
5720:
5719:
5695:
5691:
5679:
5678:
5651:
5650:
5633:
5630:
5629:
5612:
5611:
5609:
5606:
5605:
5583:
5577:
5576:
5571:
5562:
5561:
5559:
5556:
5555:
5533:
5527:
5526:
5521:
5507:
5501:
5500:
5495:
5486:
5485:
5483:
5480:
5479:
5444:
5441:
5440:
5423:
5422:
5420:
5417:
5416:
5402:
5372:
5367:
5341:
5324:
5321:
5320:
5292:
5287:
5261:
5244:
5241:
5240:
5239:has a ratio of
5224:
5221:
5220:
5186:
5183:
5182:
5133:
5116:
5113:
5112:
5096:
5093:
5092:
5070:
5067:
5066:
5017:
5000:
4997:
4996:
4980:
4977:
4976:
4954:
4951:
4950:
4907:
4890:
4887:
4886:
4843:
4826:
4823:
4822:
4803:
4800:
4799:
4768:
4765:
4764:
4736:
4733:
4732:
4692:
4675:
4672:
4671:
4655:
4652:
4651:
4629:
4626:
4625:
4590:
4587:
4586:
4570:
4567:
4566:
4544:
4541:
4540:
4524:
4521:
4520:
4506:
4450:
4442:
4439:
4438:
4401:
4397:
4386:
4375:
4354:
4353:
4315:
4312:
4311:
4274:
4270:
4259:
4248:
4227:
4226:
4188:
4185:
4184:
4147:
4143:
4105:
4102:
4101:
4056:
4053:
4052:
4042:Kenyon, Rémila
4015:
4011:
4002:
3998:
3993:
3981:
3980:
3942:
3939:
3938:
3893:
3890:
3889:
3844:
3841:
3840:
3802:
3798:
3788:
3753:
3745:
3742:
3741:
3706:
3702:
3692:
3657:
3649:
3646:
3645:
3602:
3599:
3598:
3543:
3528:
3524:
3498:
3495:
3494:
3460:
3456:
3427:
3424:
3423:
3420:Split-Fit (SF)
3367:
3363:
3337:
3334:
3333:
3325:Coffman et al.
3274:
3270:
3244:
3241:
3240:
3194:
3191:
3190:
3134:
3126:
3123:
3122:
3106:
3103:
3102:
3086:
3083:
3082:
3066:
3063:
3062:
3051:
3008:
3004:
2996:
2993:
2992:
2975:
2971:
2950:
2946:
2934:
2930:
2915:
2914:
2905:
2901:
2883:
2882:
2865:
2851:
2848:
2847:
2829:
2826:
2825:
2809:
2806:
2805:
2788:
2787:
2785:
2782:
2781:
2780:then the items
2755:
2751:
2743:
2740:
2739:
2719:
2718:
2709:
2705:
2697:
2694:
2693:
2666:
2657:
2656:
2639:
2621:
2617:
2585:
2582:
2581:
2560:
2552:
2549:
2548:
2510:
2506:
2498:
2495:
2494:
2477:
2476:
2470:
2406:
2400:
2399:
2398:
2391:
2345:
2339:
2338:
2337:
2330:
2324:
2320:
2319:
2287:
2281:
2280:
2279:
2261:
2255:
2254:
2253:
2246:
2236:
2235:
2228:
2214:
2195:
2168:
2165:
2164:
2119:
2111:
2105:
2104:
2077:
2071:
2070:
2069:
2067:
2064:
2063:
2041:
2006:
2000:
1999:
1972:
1966:
1965:
1964:
1962:
1959:
1958:
1915:
1909:
1908:
1881:
1875:
1874:
1873:
1871:
1868:
1867:
1851:
1837:
1817:
1814:
1813:
1763:
1752:
1716:
1651:
1648:
1647:
1601:
1590:
1569:
1566:
1565:
1534:
1531:
1530:
1508:
1505:
1504:
1466:
1455:
1431:
1428:
1427:
1386:
1385:
1383:
1380:
1379:
1357:
1348:
1347:
1330:
1307:
1304:
1303:
1258:
1257:
1250:
1234:
1233:
1216:
1214:
1211:
1210:
1181:
1177:
1154:
1151:
1150:
1128:
1127:
1116:
1080:
1076:
1074:
1071:
1070:
1067:
1039:
1034:
1031:
1030:
1011:
1006:
1003:
1002:
976:
971:
968:
967:
938:
935:
934:
909:
906:
905:
886:
881:
878:
877:
866:
841:hyperrectangles
819:
783:
782:
771:
765:
761:
752:
748:
740:
737:
736:
716:
712:
703:
699:
684:
680:
671:
667:
658:
654:
639:
635:
630:
625:
617:
573:
571:
568:
567:
550:
549:
541:
538:
537:
517:
512:
511:
500:
488:
484:
454:
450:
441:
437:
432:
429:
428:
427:to a position
411:
410:
402:
399:
398:
382:
355:
351:
349:
346:
345:
329:
302:
298:
296:
293:
292:
275:
274:
266:
263:
262:
245:
244:
242:
239:
238:
216:
213:
212:
182:
181:
170:
167:
166:
163:
139:
134:
131:
130:
102:
94:
91:
90:
65:
62:
61:
42:
37:
34:
33:
12:
11:
5:
16413:
16403:
16402:
16397:
16392:
16376:
16375:
16356:(3): 754–759.
16340:
16303:
16284:
16234:
16199:(5): 433–452.
16176:
16139:(2): 207–225.
16123:
16116:
16087:
16072:
16033:
16006:(4): 417–423.
15990:
15983:
15950:
15931:(4): 171–175.
15915:
15896:(3): 508–525.
15880:
15865:
15829:
15814:
15786:
15779:
15753:
15726:
15711:
15680:
15656:
15645:(1–2): 10–12.
15629:
15618:(4): 553–586.
15601:
15590:(3): 310–323.
15574:
15567:
15533:
15514:(4): 645–656.
15502:Kenyon, Claire
15493:
15486:
15455:
15444:(4): 348–368.
15428:
15417:(3): 571–582.
15392:
15362:
15351:(4): 808–826.
15345:SIAM J. Comput
15314:
15303:(2): 401–409.
15280:
15261:(3): 310–319.
15240:
15207:
15159:
15141:
15128:(2): 248–267.
15105:
15084:(4): 846–855.
15078:SIAM J. Comput
15049:
15013:
15012:
15010:
15007:
15004:
15003:
15000:
14998:
14995:
14991:
14990:
14987:
14984:
14973:
14963:
14961:
14957:
14956:
14953:
14951:
14948:
14944:
14943:
14940:
14937:
14935:
14932:
14928:
14927:
14924:
14921:
14919:
14916:
14912:
14911:
14908:
14906:
14895:
14885:
14881:
14880:
14877:
14874:
14871:
14868:
14853:
14852:
14849:
14838:
14828:
14826:
14822:
14821:
14818:
14816:
14813:
14809:
14808:
14805:
14803:
14800:
14796:
14795:
14792:
14781:
14778:
14775:
14765:
14763:
14759:
14758:
14755:
14744:
14741:
14731:
14728:
14724:
14723:
14720:
14717:
14714:
14693:
14690:
14687:
14684:
14681:
14676:
14672:
14648:
14645:
14642:
14639:
14636:
14633:
14629:
14625:
14622:
14619:
14616:
14611:
14608:
14605:
14602:
14599:
14596:
14593:
14590:
14585:
14582:
14579:
14574:
14552:
14549:
14546:
14543:
14540:
14535:
14531:
14510:
14490:
14487:
14484:
14481:
14478:
14475:
14455:
14452:
14449:
14446:
14423:
14420:
14417:
14414:
14411:
14408:
14404:
14400:
14397:
14394:
14391:
14386:
14381:
14378:
14375:
14356:online variant
14351:
14348:
14345:
14344:
14341:
14338:
14327:
14324:
14321:
14318:
14314:
14310:
14307:
14297:
14293:
14292:
14289:
14278:
14275:
14272:
14269:
14265:
14261:
14258:
14248:
14244:
14243:
14240:
14237:
14226:
14223:
14220:
14217:
14213:
14209:
14206:
14196:
14192:
14191:
14188:
14177:
14174:
14171:
14168:
14164:
14160:
14157:
14147:
14143:
14142:
14141:Jansen, Thöle
14139:
14128:
14125:
14122:
14119:
14115:
14111:
14108:
14098:
14094:
14093:
14090:
14087:
14084:
14064:
14061:
14058:
14055:
14035:
14031:
14027:
14007:
14004:
14001:
13998:
13995:
13992:
13989:
13986:
13983:
13980:
13976:
13972:
13969:
13945:
13942:
13939:
13936:
13933:
13912:
13891:
13887:
13883:
13871:
13868:
13867:
13866:
13854:
13849:
13844:
13841:
13838:
13835:
13832:
13829:
13826:
13821:
13816:
13813:
13810:
13788:
13775:
13763:
13760:
13757:
13753:
13747:
13741:
13737:
13734:
13731:
13728:
13725:
13722:
13718:
13712:
13708:
13703:
13697:
13691:
13687:
13684:
13681:
13677:
13671:
13665:
13661:
13656:
13639:
13638:
13626:
13606:
13603:
13600:
13597:
13594:
13591:
13580:
13566:
13544:
13520:
13516:
13512:
13509:
13506:
13503:
13498:
13493:
13489:
13486:
13483:
13480:
13476:
13473:
13470:
13467:
13464:
13461:
13458:
13455:
13452:
13430:
13425:
13422:
13402:
13398:
13394:
13391:
13388:
13383:
13378:
13373:
13369:
13348:
13344:
13340:
13337:
13334:
13329:
13324:
13319:
13315:
13297:
13296:
13281:
13278:
13272:
13267:
13242:
13239:
13225:
13211:
13207:
13203:
13200:
13180:
13158:
13154:
13133:
13122:
13109:
13105:
13101:
13095:
13092:
13086:
13082:
13079:
13076:
13073:
13069:
13066:
13063:
13059:
13055:
13051:
13048:
13043:
13039:
13015:
13011:
13007:
13004:
13001:
12996:
12993:
12990:
12986:
12982:
12979:
12959:
12955:
12951:
12948:
12945:
12942:
12939:
12933:
12930:
12924:
12920:
12917:
12914:
12911:
12907:
12904:
12900:
12896:
12893:
12890:
12887:
12882:
12877:
12873:
12870:
12867:
12864:
12843:
12820:
12817:
12794:
12774:
12771:
12767:
12761:
12755:
12734:
12730:
12726:
12723:
12720:
12715:
12710:
12705:
12701:
12680:
12676:
12672:
12669:
12666:
12661:
12656:
12651:
12647:
12632:
12631:
12617:
12604:
12592:
12572:
12569:
12565:
12562:
12558:
12555:
12552:
12549:
12546:
12543:
12540:
12537:
12534:
12531:
12528:
12517:
12514:
12500:
12477:
12474:
12453:
12429:
12426:
12423:
12420:
12416:
12413:
12409:
12406:
12403:
12400:
12397:
12394:
12391:
12388:
12385:
12382:
12379:
12376:
12373:
12370:
12367:
12363:
12360:
12356:
12353:
12350:
12346:
12343:
12339:
12336:
12333:
12330:
12327:
12324:
12321:
12318:
12315:
12312:
12309:
12306:
12303:
12298:
12293:
12289:
12286:
12283:
12280:
12276:
12273:
12253:
12249:
12245:
12242:
12239:
12235:
12232:
12228:
12225:
12205:
12201:
12197:
12194:
12191:
12188:
12185:
12182:
12162:
12158:
12154:
12151:
12148:
12144:
12141:
12137:
12134:
12114:
12110:
12106:
12103:
12100:
12097:
12094:
12091:
12069:
12064:
12060:
12057:
12053:
12050:
12030:
12026:
12022:
12019:
12016:
12011:
12006:
12001:
11997:
11976:
11972:
11968:
11965:
11962:
11957:
11952:
11947:
11943:
11928:
11927:
11913:
11909:
11905:
11902:
11880:
11876:
11872:
11869:
11847:
11843:
11820:
11814:
11800:
11788:
11766:
11762:
11758:
11755:
11733:
11729:
11706:
11700:
11686:
11672:
11666:
11641:
11617:
11613:
11609:
11606:
11603:
11600:
11597:
11594:
11591:
11569:
11564:
11561:
11550:
11536:
11532:
11520:
11506:
11484:
11480:
11476:
11473:
11470:
11467:
11464:
11461:
11439:
11434:
11431:
11407:
11403:
11399:
11396:
11393:
11389:
11384:
11378:
11373:
11369:
11342:
11339:
11336:
11313:
11310:
11307:
11304:
11301:
11298:
11295:
11290:
11286:
11282:
11279:
11257:
11253:
11249:
11246:
11243:
11238:
11233:
11228:
11224:
11220:
11217:
11212:
11208:
11204:
11201:
11198:
11193:
11188:
11183:
11179:
11175:
11172:
11169:
11166:
11163:
11160:
11157:
11154:
11149:
11144:
11140:
11137:
11134:
11131:
11110:
11107:
11104:
11099:
11094:
11089:
11085:
11064:
11061:
11058:
11053:
11048:
11043:
11039:
11016:
11013:
11010:
11007:
11004:
11001:
10998:
10995:
10988:
10983:
10980:
10976:
10972:
10969:
10964:
10959:
10955:
10952:
10949:
10946:
10923:
10901:
10896:
10891:
10886:
10882:
10859:
10837:
10832:
10827:
10822:
10818:
10795:
10773:
10753:
10731:
10717:
10714:
10713:
10712:
10700:
10695:
10690:
10687:
10684:
10681:
10678:
10675:
10672:
10667:
10662:
10659:
10656:
10634:
10621:
10608:
10602:
10596:
10575:
10570:
10565:
10558:
10552:
10548:
10543:
10526:
10525:
10513:
10501:
10500:
10499:
10487:
10466:
10463:
10442:
10419:
10416:
10413:
10410:
10407:
10402:
10398:
10384:
10371:
10368:
10347:
10324:
10321:
10318:
10315:
10312:
10307:
10303:
10275:
10271:
10249:
10246:
10224:
10221:
10199:
10177:
10173:
10169:
10166:
10161:
10157:
10143:
10131:
10126:
10122:
10118:
10113:
10109:
10105:
10102:
10099:
10094:
10090:
10069:
10049:
10029:
10009:
9987:
9983:
9971:
9959:
9955:
9951:
9939:
9921:
9917:
9913:
9908:
9904:
9900:
9895:
9891:
9868:
9864:
9852:
9834:
9830:
9818:
9804:
9800:
9788:
9774:
9770:
9747:
9743:
9722:
9718:
9714:
9690:
9668:
9643:
9638:
9634:
9630:
9625:
9621:
9617:
9597:
9592:
9588:
9584:
9579:
9575:
9571:
9549:
9544:
9541:
9529:
9526:
9525:
9524:
9512:
9509:
9506:
9501:
9496:
9493:
9490:
9487:
9484:
9481:
9478:
9475:
9472:
9469:
9466:
9461:
9456:
9453:
9450:
9428:
9406:
9403:
9400:
9380:
9377:
9374:
9363:
9351:
9346:
9341:
9338:
9335:
9332:
9329:
9326:
9323:
9320:
9317:
9314:
9311:
9306:
9301:
9298:
9295:
9273:
9251:
9248:
9245:
9234:
9222:
9217:
9212:
9209:
9206:
9203:
9200:
9197:
9192:
9188:
9184:
9181:
9176:
9171:
9168:
9165:
9162:
9159:
9156:
9153:
9148:
9143:
9140:
9137:
9128:it holds that
9115:
9102:
9089:
9083:
9077:
9056:
9051:
9046:
9039:
9033:
9029:
9024:
8934:
8886:
8866:
8846:
8826:
8806:
8793:
8790:
8789:
8788:
8774:
8750:
8746:
8725:
8720:
8715:
8712:
8709:
8706:
8703:
8700:
8697:
8693:
8687:
8683:
8679:
8676:
8671:
8666:
8663:
8660:
8657:
8654:
8651:
8648:
8643:
8638:
8635:
8613:
8600:
8588:
8584:
8578:
8572:
8568:
8563:
8541:
8538:
8534:
8528:
8522:
8518:
8515:
8512:
8508:
8502:
8496:
8492:
8487:
8470:
8469:
8454:
8450:
8427:
8423:
8402:
8398:
8394:
8372:
8368:
8345:
8341:
8329:
8317:
8313:
8309:
8298:
8284:
8280:
8268:
8265:
8251:
8247:
8224:
8220:
8199:
8195:
8191:
8167:
8145:
8131:
8128:
8127:
8126:
8114:
8109:
8104:
8101:
8098:
8095:
8091:
8087:
8084:
8081:
8078:
8075:
8072:
8069:
8065:
8061:
8058:
8055:
8052:
8049:
8045:
8041:
8038:
8033:
8028:
8025:
8022:
8000:
7978:
7975:
7972:
7961:
7948:
7944:
7940:
7937:
7934:
7929:
7924:
7921:
7918:
7915:
7912:
7909:
7905:
7901:
7898:
7895:
7892:
7887:
7882:
7879:
7876:
7856:
7853:
7850:
7828:
7824:
7820:
7817:
7814:
7809:
7804:
7801:
7798:
7795:
7792:
7789:
7786:
7783:
7780:
7776:
7772:
7769:
7766:
7763:
7760:
7757:
7754:
7749:
7744:
7741:
7738:
7718:
7696:
7679:
7678:
7666:
7644:
7641:
7638:
7635:
7632:
7629:
7623:
7609:
7597:
7594:
7591:
7588:
7585:
7581:
7577:
7557:
7546:
7534:
7531:
7528:
7525:
7522:
7518:
7514:
7511:
7508:
7505:
7502:
7499:
7488:
7474:
7471:
7468:
7465:
7459:
7445:
7431:
7428:
7425:
7422:
7419:
7416:
7410:
7385:
7382:
7379:
7376:
7370:
7356:
7344:
7341:
7338:
7335:
7332:
7328:
7324:
7321:
7318:
7315:
7312:
7309:
7287:
7284:
7281:
7278:
7275:
7272:
7266:
7243:
7240:
7237:
7234:
7231:
7227:
7223:
7220:
7217:
7214:
7211:
7208:
7186:
7181:
7178:
7156:
7153:
7150:
7147:
7141:
7116:
7113:
7110:
7107:
7104:
7101:
7095:
7070:
7067:
7064:
7061:
7055:
7043:into two sets
7030:
7017:
7005:
7001:
6997:
6976:
6972:
6969:
6945:
6923:
6909:
6906:
6905:
6904:
6901:
6889:
6884:
6879:
6876:
6873:
6870:
6866:
6862:
6859:
6856:
6852:
6848:
6844:
6840:
6837:
6832:
6827:
6824:
6821:
6818:
6815:
6793:
6771:
6768:
6765:
6743:
6739:
6735:
6732:
6727:
6722:
6719:
6716:
6713:
6710:
6707:
6703:
6699:
6696:
6693:
6690:
6685:
6680:
6677:
6674:
6671:
6668:
6646:
6633:
6621:
6616:
6611:
6608:
6605:
6602:
6598:
6594:
6591:
6588:
6584:
6580:
6577:
6574:
6570:
6566:
6563:
6558:
6553:
6550:
6547:
6544:
6541:
6519:
6497:
6494:
6491:
6469:
6465:
6461:
6458:
6453:
6448:
6445:
6442:
6439:
6435:
6431:
6427:
6423:
6420:
6417:
6413:
6409:
6406:
6401:
6396:
6393:
6390:
6387:
6384:
6362:
6357:
6354:
6334:
6330:
6326:
6323:
6320:
6317:
6314:
6311:
6291:
6269:
6247:
6244:
6241:
6230:
6216:
6192:
6188:
6167:
6162:
6157:
6154:
6151:
6148:
6145:
6142:
6137:
6133:
6129:
6126:
6121:
6116:
6113:
6110:
6107:
6104:
6101:
6098:
6093:
6088:
6085:
6082:
6079:
6076:
6054:
6041:
6028:
6022:
6016:
5995:
5990:
5985:
5978:
5972:
5968:
5963:
5941:
5938:
5937:
5936:
5933:
5922:
5919:
5914:
5909:
5906:
5903:
5900:
5897:
5894:
5891:
5888:
5885:
5882:
5879:
5875:
5869:
5864:
5861:
5858:
5855:
5852:
5830:
5808:
5805:
5802:
5791:
5777:
5753:
5749:
5728:
5723:
5718:
5715:
5712:
5709:
5706:
5703:
5698:
5694:
5690:
5687:
5682:
5677:
5674:
5671:
5668:
5665:
5662:
5659:
5654:
5649:
5646:
5643:
5640:
5637:
5615:
5602:
5590:
5586:
5580:
5574:
5570:
5565:
5543:
5540:
5536:
5530:
5524:
5520:
5517:
5514:
5510:
5504:
5498:
5494:
5489:
5460:
5457:
5454:
5451:
5448:
5426:
5401:
5398:
5397:
5396:
5381:
5378:
5375:
5371:
5366:
5363:
5360:
5357:
5354:
5351:
5348:
5344:
5340:
5337:
5334:
5331:
5328:
5301:
5298:
5295:
5291:
5286:
5283:
5280:
5277:
5274:
5271:
5268:
5264:
5260:
5257:
5254:
5251:
5248:
5228:
5208:
5205:
5202:
5199:
5196:
5193:
5190:
5179:
5167:
5164:
5161:
5158:
5155:
5152:
5149:
5146:
5143:
5140:
5136:
5132:
5129:
5126:
5123:
5120:
5100:
5080:
5077:
5074:
5063:
5051:
5048:
5045:
5042:
5039:
5036:
5033:
5030:
5027:
5024:
5020:
5016:
5013:
5010:
5007:
5004:
4984:
4964:
4961:
4958:
4947:
4935:
4932:
4929:
4926:
4923:
4920:
4917:
4914:
4910:
4906:
4903:
4900:
4897:
4894:
4883:
4871:
4868:
4865:
4862:
4859:
4856:
4853:
4850:
4846:
4842:
4839:
4836:
4833:
4830:
4819:
4807:
4787:
4784:
4781:
4778:
4775:
4772:
4752:
4749:
4746:
4743:
4740:
4720:
4717:
4714:
4711:
4708:
4705:
4702:
4699:
4695:
4691:
4688:
4685:
4682:
4679:
4659:
4639:
4636:
4633:
4617:in the strip.
4606:
4603:
4600:
4597:
4594:
4574:
4554:
4551:
4548:
4528:
4505:
4502:
4499:
4498:
4497:Harren et al.
4495:
4484:
4481:
4478:
4475:
4472:
4469:
4466:
4463:
4460:
4457:
4453:
4449:
4446:
4436:
4434:
4430:
4429:
4426:
4415:
4412:
4409:
4404:
4400:
4396:
4393:
4389:
4385:
4382:
4378:
4374:
4371:
4368:
4365:
4362:
4357:
4352:
4349:
4346:
4343:
4340:
4337:
4334:
4331:
4328:
4325:
4322:
4319:
4309:
4307:
4303:
4302:
4299:
4288:
4285:
4282:
4277:
4273:
4269:
4266:
4262:
4258:
4255:
4251:
4247:
4244:
4241:
4238:
4235:
4230:
4225:
4222:
4219:
4216:
4213:
4210:
4207:
4204:
4201:
4198:
4195:
4192:
4182:
4180:
4176:
4175:
4172:
4161:
4158:
4155:
4150:
4146:
4142:
4139:
4136:
4133:
4130:
4127:
4124:
4121:
4118:
4115:
4112:
4109:
4099:
4097:
4093:
4092:
4089:
4078:
4075:
4072:
4069:
4066:
4063:
4060:
4050:
4048:
4044:
4043:
4040:
4029:
4026:
4023:
4018:
4014:
4010:
4005:
4001:
3996:
3992:
3989:
3984:
3979:
3976:
3973:
3970:
3967:
3964:
3961:
3958:
3955:
3952:
3949:
3946:
3936:
3934:
3930:
3929:
3926:
3915:
3912:
3909:
3906:
3903:
3900:
3897:
3887:
3885:
3881:
3880:
3877:
3866:
3863:
3860:
3857:
3854:
3851:
3848:
3838:
3835:
3831:
3830:
3827:
3816:
3813:
3810:
3805:
3801:
3795:
3792:
3787:
3784:
3781:
3778:
3775:
3772:
3769:
3766:
3763:
3760:
3756:
3752:
3749:
3739:
3736:
3732:
3731:
3720:
3717:
3714:
3709:
3705:
3699:
3696:
3691:
3688:
3685:
3682:
3679:
3676:
3673:
3670:
3667:
3664:
3660:
3656:
3653:
3643:
3639:
3638:
3635:
3624:
3621:
3618:
3615:
3612:
3609:
3606:
3596:
3593:
3589:
3588:
3585:
3574:
3571:
3568:
3565:
3562:
3559:
3556:
3553:
3550:
3546:
3542:
3539:
3536:
3531:
3527:
3523:
3520:
3517:
3514:
3511:
3508:
3505:
3502:
3492:
3490:
3486:
3485:
3474:
3471:
3468:
3463:
3459:
3455:
3452:
3449:
3446:
3443:
3440:
3437:
3434:
3431:
3421:
3417:
3416:
3405:
3402:
3399:
3396:
3393:
3390:
3387:
3384:
3381:
3378:
3375:
3370:
3366:
3362:
3359:
3356:
3353:
3350:
3347:
3344:
3341:
3331:
3327:
3326:
3323:
3312:
3309:
3306:
3303:
3300:
3297:
3294:
3291:
3288:
3285:
3282:
3277:
3273:
3269:
3266:
3263:
3260:
3257:
3254:
3251:
3248:
3238:
3235:
3231:
3230:
3227:
3216:
3213:
3210:
3207:
3204:
3201:
3198:
3188:
3185:
3181:
3180:
3177:
3174:
3171:
3150:
3147:
3144:
3141:
3137:
3133:
3130:
3110:
3090:
3070:
3050:
3047:
3034:
3031:
3028:
3025:
3022:
3019:
3016:
3011:
3007:
3003:
3000:
2978:
2974:
2970:
2967:
2964:
2961:
2958:
2953:
2949:
2945:
2942:
2937:
2933:
2929:
2926:
2923:
2918:
2913:
2908:
2904:
2900:
2897:
2894:
2891:
2886:
2881:
2877:
2874:
2871:
2868:
2864:
2861:
2858:
2855:
2833:
2813:
2791:
2769:
2766:
2763:
2758:
2754:
2750:
2747:
2727:
2722:
2717:
2712:
2708:
2704:
2701:
2679:
2676:
2673:
2669:
2665:
2660:
2655:
2651:
2648:
2645:
2642:
2638:
2635:
2632:
2629:
2624:
2620:
2616:
2613:
2610:
2607:
2604:
2601:
2598:
2595:
2592:
2589:
2563:
2559:
2556:
2536:
2533:
2530:
2527:
2524:
2521:
2518:
2513:
2509:
2505:
2502:
2480:
2473:
2468:
2463:
2458:
2455:
2452:
2449:
2446:
2443:
2440:
2437:
2434:
2431:
2428:
2425:
2420:
2417:
2414:
2409:
2403:
2397:
2394:
2390:
2386:
2383:
2380:
2377:
2374:
2371:
2368:
2365:
2362:
2359:
2356:
2353:
2348:
2342:
2336:
2333:
2329:
2323:
2318:
2315:
2312:
2309:
2306:
2301:
2298:
2295:
2290:
2284:
2278:
2275:
2272:
2269:
2264:
2258:
2252:
2249:
2245:
2239:
2231:
2227:
2224:
2221:
2217:
2213:
2210:
2207:
2204:
2201:
2198:
2194:
2190:
2187:
2184:
2181:
2178:
2175:
2172:
2150:
2147:
2144:
2141:
2138:
2135:
2132:
2129:
2126:
2122:
2118:
2114:
2108:
2103:
2100:
2097:
2094:
2091:
2088:
2085:
2080:
2074:
2051:
2048:
2044:
2040:
2037:
2034:
2031:
2028:
2025:
2022:
2019:
2016:
2013:
2009:
2003:
1998:
1995:
1992:
1989:
1986:
1983:
1980:
1975:
1969:
1946:
1943:
1940:
1937:
1934:
1931:
1928:
1925:
1922:
1918:
1912:
1907:
1904:
1901:
1898:
1895:
1892:
1889:
1884:
1878:
1854:
1850:
1847:
1844:
1840:
1836:
1833:
1830:
1827:
1824:
1821:
1798:
1795:
1792:
1789:
1786:
1783:
1780:
1775:
1772:
1769:
1766:
1761:
1758:
1755:
1751:
1747:
1744:
1741:
1738:
1735:
1732:
1729:
1726:
1723:
1719:
1715:
1712:
1709:
1706:
1703:
1700:
1697:
1694:
1691:
1688:
1685:
1682:
1679:
1676:
1673:
1670:
1667:
1664:
1661:
1658:
1655:
1633:
1630:
1627:
1624:
1621:
1618:
1613:
1610:
1607:
1604:
1599:
1596:
1593:
1589:
1585:
1582:
1579:
1576:
1573:
1553:
1550:
1547:
1544:
1541:
1538:
1518:
1515:
1512:
1492:
1489:
1486:
1483:
1480:
1477:
1474:
1469:
1464:
1461:
1458:
1454:
1450:
1447:
1444:
1441:
1438:
1435:
1415:
1412:
1409:
1406:
1403:
1400:
1397:
1394:
1389:
1364:
1360:
1356:
1351:
1346:
1342:
1339:
1336:
1333:
1329:
1326:
1323:
1320:
1317:
1314:
1311:
1289:
1286:
1283:
1280:
1277:
1274:
1271:
1268:
1261:
1256:
1253:
1249:
1245:
1242:
1237:
1232:
1228:
1225:
1222:
1219:
1195:
1192:
1189:
1184:
1180:
1176:
1173:
1170:
1167:
1164:
1161:
1158:
1136:
1131:
1126:
1123:
1119:
1115:
1112:
1109:
1106:
1103:
1100:
1097:
1094:
1091:
1088:
1083:
1079:
1066:
1063:
1046:
1042:
1038:
1018:
1014:
1010:
983:
979:
975:
951:
948:
945:
942:
922:
919:
916:
913:
893:
889:
885:
865:
862:
818:
815:
791:
786:
781:
778:
774:
768:
764:
760:
755:
751:
747:
744:
724:
719:
715:
711:
706:
702:
698:
695:
692:
687:
683:
679:
674:
670:
666:
661:
657:
653:
650:
647:
642:
638:
633:
628:
624:
620:
616:
613:
610:
607:
604:
601:
598:
595:
592:
589:
586:
582:
579:
576:
553:
548:
545:
523:
520:
515:
510:
507:
503:
499:
496:
491:
487:
483:
480:
477:
474:
471:
468:
465:
462:
457:
453:
449:
444:
440:
436:
414:
409:
406:
385:
381:
378:
375:
372:
369:
366:
363:
358:
354:
344:and a height
332:
328:
325:
322:
319:
316:
313:
310:
305:
301:
278:
273:
270:
248:
226:
223:
220:
196:
193:
190:
185:
180:
177:
174:
162:
159:
146:
142:
138:
118:
115:
112:
109:
105:
101:
98:
78:
75:
72:
69:
49:
45:
41:
9:
6:
4:
3:
2:
16412:
16401:
16398:
16396:
16393:
16391:
16388:
16387:
16385:
16371:
16367:
16363:
16359:
16355:
16351:
16344:
16336:
16332:
16327:
16322:
16318:
16314:
16307:
16299:
16295:
16288:
16280:
16276:
16272:
16268:
16264:
16260:
16256:
16252:
16245:
16238:
16230:
16226:
16222:
16218:
16214:
16210:
16206:
16202:
16198:
16194:
16187:
16180:
16172:
16168:
16164:
16160:
16155:
16150:
16146:
16142:
16138:
16134:
16127:
16119:
16113:
16109:
16105:
16101:
16094:
16092:
16083:
16079:
16075:
16069:
16065:
16061:
16056:
16051:
16047:
16040:
16038:
16029:
16025:
16021:
16017:
16013:
16009:
16005:
16001:
15994:
15986:
15980:
15976:
15972:
15968:
15961:
15954:
15946:
15942:
15938:
15934:
15930:
15926:
15919:
15911:
15907:
15903:
15899:
15895:
15891:
15884:
15876:
15872:
15868:
15862:
15858:
15854:
15849:
15844:
15840:
15833:
15825:
15821:
15817:
15815:9783959770279
15811:
15806:
15801:
15797:
15790:
15782:
15776:
15772:
15768:
15764:
15757:
15749:
15745:
15741:
15737:
15730:
15722:
15718:
15714:
15712:9783959771245
15708:
15703:
15698:
15694:
15687:
15685:
15676:
15671:
15667:
15660:
15652:
15648:
15644:
15640:
15633:
15625:
15621:
15617:
15613:
15605:
15597:
15593:
15589:
15585:
15578:
15570:
15564:
15560:
15556:
15552:
15548:
15544:
15537:
15529:
15525:
15521:
15517:
15513:
15509:
15508:
15503:
15497:
15489:
15483:
15479:
15475:
15471:
15464:
15462:
15460:
15451:
15447:
15443:
15439:
15432:
15424:
15420:
15416:
15412:
15405:
15403:
15401:
15399:
15397:
15388:
15384:
15380:
15376:
15369:
15367:
15358:
15354:
15350:
15346:
15339:
15337:
15335:
15333:
15331:
15329:
15327:
15325:
15323:
15321:
15319:
15310:
15306:
15302:
15298:
15291:
15289:
15287:
15285:
15276:
15272:
15268:
15264:
15260:
15256:
15249:
15247:
15245:
15235:
15230:
15226:
15222:
15218:
15211:
15203:
15199:
15195:
15191:
15186:
15181:
15177:
15173:
15166:
15164:
15152:
15145:
15136:
15131:
15127:
15123:
15119:
15112:
15110:
15101:
15097:
15092:
15087:
15083:
15079:
15072:
15070:
15068:
15066:
15064:
15062:
15060:
15058:
15056:
15054:
15045:
15041:
15037:
15033:
15029:
15025:
15018:
15014:
15001:
14999:
14996:
14993:
14992:
14988:
14985:
14971:
14964:
14962:
14959:
14958:
14954:
14952:
14949:
14946:
14945:
14941:
14938:
14936:
14933:
14930:
14929:
14925:
14922:
14920:
14917:
14914:
14913:
14909:
14907:
14893:
14886:
14883:
14882:
14878:
14875:
14872:
14869:
14866:
14865:
14859:
14850:
14836:
14829:
14827:
14824:
14823:
14819:
14817:
14814:
14811:
14810:
14806:
14804:
14801:
14798:
14797:
14793:
14779:
14776:
14773:
14766:
14764:
14761:
14760:
14756:
14742:
14739:
14732:
14729:
14726:
14725:
14721:
14718:
14715:
14712:
14711:
14705:
14691:
14688:
14682:
14670:
14660:
14643:
14637:
14634:
14631:
14627:
14620:
14614:
14600:
14594:
14591:
14588:
14564:
14550:
14547:
14541:
14529:
14508:
14485:
14479:
14476:
14473:
14450:
14444:
14435:
14418:
14412:
14409:
14406:
14402:
14395:
14389:
14384:
14363:
14360:
14357:
14342:
14339:
14322:
14319:
14316:
14312:
14308:
14298:
14295:
14294:
14290:
14273:
14270:
14267:
14263:
14259:
14249:
14246:
14245:
14241:
14238:
14221:
14218:
14215:
14211:
14207:
14197:
14194:
14193:
14189:
14172:
14169:
14166:
14162:
14158:
14148:
14145:
14144:
14140:
14123:
14120:
14117:
14113:
14109:
14099:
14096:
14095:
14091:
14088:
14085:
14082:
14081:
14075:
14062:
14059:
14056:
14053:
14033:
14029:
14025:
14002:
13996:
13993:
13990:
13984:
13981:
13978:
13974:
13970:
13957:
13940:
13934:
13931:
13910:
13889:
13885:
13881:
13839:
13836:
13833:
13830:
13827:
13811:
13808:
13776:
13732:
13729:
13723:
13720:
13716:
13710:
13682:
13679:
13644:
13643:
13642:
13624:
13601:
13595:
13592:
13589:
13581:
13542:
13534:
13533:
13532:
13518:
13514:
13510:
13507:
13504:
13474:
13468:
13462:
13456:
13450:
13423:
13420:
13400:
13396:
13392:
13389:
13367:
13346:
13342:
13338:
13335:
13313:
13304:
13300:
13279:
13240:
13226:
13209:
13205:
13201:
13198:
13178:
13156:
13152:
13131:
13123:
13107:
13103:
13093:
13067:
13064:
13061:
13057:
13053:
13046:
13041:
13037:
13028:
13027:
13026:
13013:
13009:
13005:
13002:
12994:
12991:
12988:
12984:
12977:
12957:
12953:
12949:
12946:
12943:
12940:
12931:
12905:
12902:
12898:
12894:
12891:
12888:
12841:
12834:as the first
12818:
12792:
12772:
12769:
12732:
12728:
12724:
12721:
12699:
12678:
12674:
12670:
12667:
12645:
12636:
12605:
12590:
12563:
12560:
12553:
12550:
12544:
12538:
12529:
12526:
12518:
12515:
12475:
12472:
12451:
12443:
12442:
12441:
12427:
12414:
12411:
12404:
12401:
12395:
12389:
12380:
12377:
12371:
12361:
12358:
12351:
12344:
12341:
12334:
12331:
12325:
12319:
12313:
12307:
12304:
12271:
12251:
12247:
12243:
12240:
12233:
12230:
12223:
12203:
12199:
12195:
12192:
12186:
12180:
12160:
12156:
12152:
12149:
12142:
12139:
12132:
12112:
12108:
12104:
12101:
12095:
12089:
12062:
12058:
12055:
12051:
12048:
12028:
12024:
12020:
12017:
11995:
11974:
11970:
11966:
11963:
11941:
11932:
11911:
11907:
11903:
11900:
11878:
11874:
11870:
11867:
11845:
11841:
11818:
11801:
11786:
11764:
11760:
11756:
11753:
11731:
11727:
11704:
11687:
11670:
11615:
11611:
11607:
11604:
11601:
11595:
11589:
11562:
11559:
11551:
11534:
11530:
11521:
11482:
11478:
11474:
11471:
11465:
11459:
11432:
11429:
11421:
11420:
11419:
11405:
11401:
11397:
11394:
11387:
11367:
11358:
11354:
11340:
11337:
11334:
11325:
11308:
11305:
11302:
11293:
11288:
11280:
11255:
11247:
11244:
11222:
11218:
11210:
11202:
11199:
11177:
11173:
11167:
11164:
11161:
11158:
11155:
11108:
11105:
11083:
11062:
11059:
11037:
11028:
11011:
11005:
10999:
10993:
10981:
10978:
10974:
10970:
10880:
10816:
10808:we denote by
10771:
10751:
10685:
10682:
10679:
10676:
10673:
10657:
10654:
10622:
10568:
10531:
10530:
10529:
10511:
10502:
10485:
10464:
10461:
10440:
10432:
10414:
10408:
10405:
10400:
10396:
10388:
10385:
10369:
10366:
10345:
10337:
10319:
10313:
10310:
10305:
10301:
10293:
10290:
10289:
10273:
10269:
10247:
10244:
10222:
10219:
10197:
10190:
10175:
10171:
10167:
10164:
10159:
10155:
10147:
10144:
10124:
10120:
10116:
10111:
10107:
10097:
10092:
10088:
10067:
10047:
10027:
10007:
9985:
9981:
9972:
9957:
9953:
9949:
9940:
9937:
9919:
9915:
9911:
9902:
9898:
9893:
9889:
9866:
9862:
9853:
9850:
9832:
9828:
9819:
9798:
9789:
9772:
9768:
9745:
9741:
9720:
9716:
9712:
9704:
9703:
9702:
9688:
9655:
9636:
9632:
9628:
9623:
9619:
9590:
9586:
9582:
9577:
9573:
9542:
9539:
9510:
9507:
9491:
9488:
9485:
9479:
9476:
9473:
9467:
9451:
9448:
9404:
9401:
9398:
9378:
9375:
9372:
9364:
9336:
9333:
9330:
9324:
9321:
9318:
9312:
9296:
9293:
9249:
9246:
9243:
9235:
9207:
9204:
9201:
9198:
9195:
9186:
9182:
9166:
9163:
9160:
9157:
9154:
9138:
9135:
9103:
9049:
9012:
9011:
9010:
9006:
9003:
8998:
8995:
8991:
8987:
8984:
8981:S_2 is empty
8980:
8977:
8973:
8969:
8965:
8960:
8957:
8954:
8944:
8941:
8937:
8933:
8898:
8884:
8864:
8844:
8824:
8804:
8744:
8710:
8707:
8704:
8701:
8698:
8695:
8691:
8681:
8677:
8661:
8658:
8655:
8652:
8649:
8633:
8601:
8513:
8510:
8475:
8474:
8473:
8452:
8448:
8425:
8421:
8400:
8396:
8392:
8370:
8366:
8343:
8339:
8330:
8315:
8311:
8307:
8299:
8282:
8278:
8269:
8266:
8249:
8245:
8222:
8218:
8197:
8193:
8189:
8181:
8180:
8179:
8165:
8099:
8096:
8093:
8089:
8085:
8082:
8076:
8073:
8070:
8063:
8056:
8053:
8050:
8043:
8039:
8023:
8020:
7976:
7973:
7970:
7962:
7942:
7938:
7935:
7919:
7916:
7913:
7907:
7903:
7899:
7893:
7877:
7874:
7854:
7851:
7848:
7822:
7818:
7815:
7799:
7796:
7793:
7787:
7784:
7781:
7774:
7767:
7764:
7761:
7755:
7739:
7736:
7716:
7684:
7683:
7682:
7664:
7642:
7639:
7636:
7633:
7630:
7627:
7610:
7592:
7589:
7586:
7579:
7575:
7555:
7547:
7529:
7526:
7523:
7516:
7509:
7506:
7503:
7497:
7489:
7472:
7469:
7466:
7463:
7446:
7429:
7426:
7423:
7420:
7417:
7414:
7383:
7380:
7377:
7374:
7357:
7339:
7336:
7333:
7326:
7322:
7319:
7313:
7307:
7285:
7282:
7279:
7276:
7273:
7270:
7238:
7235:
7232:
7225:
7221:
7218:
7212:
7206:
7199:with a width
7179:
7176:
7154:
7151:
7148:
7145:
7114:
7111:
7108:
7105:
7102:
7099:
7068:
7065:
7062:
7059:
7018:
7003:
6999:
6995:
6970:
6967:
6959:
6958:
6957:
6943:
6902:
6874:
6871:
6868:
6864:
6860:
6857:
6854:
6850:
6846:
6842:
6838:
6822:
6819:
6816:
6813:
6769:
6766:
6763:
6737:
6733:
6717:
6714:
6711:
6705:
6701:
6697:
6691:
6675:
6672:
6669:
6666:
6634:
6606:
6603:
6600:
6596:
6592:
6589:
6586:
6582:
6578:
6575:
6572:
6568:
6564:
6548:
6545:
6542:
6539:
6495:
6492:
6489:
6463:
6459:
6443:
6440:
6437:
6433:
6429:
6425:
6421:
6418:
6415:
6411:
6407:
6391:
6388:
6385:
6382:
6355:
6352:
6332:
6328:
6324:
6321:
6315:
6309:
6289:
6245:
6242:
6239:
6231:
6186:
6152:
6149:
6146:
6143:
6140:
6131:
6127:
6111:
6108:
6105:
6102:
6099:
6083:
6080:
6077:
6074:
6042:
5988:
5951:
5950:
5949:
5946:
5934:
5920:
5904:
5901:
5898:
5892:
5889:
5886:
5880:
5859:
5856:
5853:
5850:
5806:
5803:
5800:
5792:
5747:
5713:
5710:
5707:
5704:
5701:
5692:
5688:
5672:
5669:
5666:
5663:
5660:
5644:
5641:
5638:
5635:
5603:
5515:
5512:
5477:
5476:
5475:
5472:
5455:
5452:
5449:
5413:
5406:
5379:
5376:
5373:
5369:
5364:
5358:
5352:
5349:
5346:
5342:
5335:
5329:
5326:
5318:
5299:
5296:
5293:
5289:
5284:
5278:
5272:
5269:
5266:
5262:
5255:
5249:
5246:
5226:
5203:
5200:
5197:
5191:
5188:
5180:
5165:
5162:
5159:
5156:
5150:
5144:
5141:
5138:
5134:
5127:
5121:
5118:
5098:
5078:
5075:
5072:
5064:
5049:
5046:
5043:
5040:
5034:
5028:
5025:
5022:
5018:
5011:
5005:
5002:
4982:
4962:
4959:
4956:
4948:
4933:
4930:
4924:
4918:
4915:
4912:
4908:
4901:
4895:
4892:
4884:
4869:
4866:
4860:
4854:
4851:
4848:
4844:
4837:
4831:
4828:
4820:
4805:
4782:
4776:
4773:
4770:
4747:
4741:
4738:
4718:
4715:
4709:
4703:
4700:
4697:
4693:
4686:
4680:
4677:
4657:
4637:
4634:
4631:
4623:
4622:
4621:
4618:
4601:
4598:
4595:
4572:
4552:
4549:
4546:
4526:
4517:
4510:
4496:
4479:
4473:
4470:
4467:
4461:
4458:
4455:
4451:
4447:
4437:
4435:
4432:
4431:
4427:
4410:
4398:
4391:
4387:
4380:
4376:
4372:
4366:
4363:
4350:
4344:
4338:
4335:
4332:
4326:
4323:
4320:
4310:
4308:
4305:
4304:
4300:
4283:
4271:
4264:
4260:
4253:
4249:
4245:
4239:
4236:
4223:
4217:
4211:
4208:
4205:
4199:
4196:
4193:
4183:
4181:
4178:
4177:
4173:
4156:
4144:
4140:
4134:
4128:
4125:
4122:
4116:
4113:
4110:
4100:
4098:
4095:
4094:
4090:
4073:
4067:
4064:
4061:
4058:
4051:
4049:
4046:
4045:
4041:
4024:
4012:
4003:
3999:
3994:
3990:
3977:
3971:
3965:
3962:
3959:
3953:
3950:
3947:
3937:
3935:
3932:
3931:
3927:
3910:
3904:
3901:
3898:
3895:
3888:
3886:
3883:
3882:
3878:
3861:
3855:
3852:
3849:
3846:
3839:
3836:
3833:
3832:
3829:Baker et al.
3828:
3811:
3799:
3793:
3790:
3785:
3782:
3776:
3770:
3767:
3764:
3758:
3754:
3750:
3740:
3737:
3734:
3733:
3715:
3703:
3697:
3694:
3689:
3686:
3680:
3674:
3671:
3668:
3662:
3658:
3654:
3644:
3641:
3640:
3619:
3613:
3610:
3607:
3604:
3597:
3594:
3590:
3586:
3569:
3563:
3560:
3557:
3554:
3551:
3548:
3544:
3537:
3525:
3521:
3515:
3509:
3506:
3503:
3500:
3493:
3491:
3488:
3487:
3469:
3457:
3453:
3450:
3444:
3438:
3435:
3432:
3429:
3422:
3419:
3418:
3400:
3394:
3391:
3388:
3385:
3382:
3376:
3364:
3360:
3354:
3348:
3345:
3342:
3339:
3332:
3329:
3328:
3307:
3301:
3298:
3295:
3292:
3289:
3283:
3271:
3267:
3261:
3255:
3252:
3249:
3246:
3239:
3236:
3232:
3229:Baker et al.
3228:
3211:
3205:
3202:
3199:
3196:
3189:
3186:
3183:
3182:
3178:
3175:
3172:
3169:
3168:
3162:
3145:
3142:
3139:
3135:
3131:
3108:
3088:
3068:
3060:
3056:
3046:
3029:
3026:
3023:
3014:
3009:
3001:
2976:
2968:
2965:
2959:
2947:
2943:
2935:
2927:
2924:
2902:
2898:
2892:
2862:
2859:
2856:
2853:
2845:
2831:
2811:
2764:
2752:
2748:
2745:
2706:
2702:
2699:
2690:
2677:
2671:
2667:
2636:
2630:
2618:
2608:
2605:
2599:
2593:
2590:
2587:
2579:
2576:
2557:
2554:
2531:
2528:
2525:
2516:
2511:
2503:
2471:
2466:
2461:
2453:
2447:
2438:
2432:
2429:
2426:
2415:
2407:
2395:
2392:
2388:
2384:
2378:
2372:
2366:
2360:
2354:
2346:
2334:
2331:
2327:
2321:
2316:
2310:
2304:
2296:
2288:
2276:
2270:
2262:
2250:
2247:
2243:
2225:
2219:
2215:
2211:
2208:
2205:
2199:
2196:
2188:
2182:
2176:
2173:
2170:
2162:
2145:
2142:
2136:
2130:
2127:
2124:
2120:
2116:
2101:
2098:
2092:
2086:
2078:
2046:
2042:
2038:
2035:
2029:
2023:
2020:
2017:
2014:
2011:
1996:
1993:
1987:
1981:
1973:
1941:
1938:
1935:
1932:
1926:
1920:
1905:
1902:
1896:
1890:
1882:
1848:
1842:
1838:
1834:
1831:
1828:
1822:
1819:
1810:
1793:
1790:
1784:
1778:
1770:
1764:
1759:
1756:
1753:
1749:
1745:
1739:
1733:
1730:
1727:
1724:
1721:
1707:
1701:
1695:
1692:
1686:
1680:
1671:
1665:
1659:
1656:
1653:
1645:
1631:
1628:
1622:
1616:
1608:
1602:
1597:
1594:
1591:
1587:
1583:
1577:
1571:
1551:
1548:
1542:
1536:
1516:
1513:
1510:
1487:
1484:
1478:
1472:
1467:
1462:
1459:
1456:
1452:
1448:
1445:
1436:
1433:
1407:
1401:
1398:
1395:
1376:
1362:
1358:
1327:
1321:
1315:
1312:
1309:
1301:
1284:
1278:
1272:
1266:
1254:
1251:
1247:
1243:
1207:
1190:
1178:
1174:
1168:
1162:
1159:
1156:
1148:
1124:
1121:
1110:
1104:
1095:
1089:
1077:
1062:
1060:
1044:
1040:
1036:
1016:
1012:
1008:
1000:
997:
981:
977:
973:
965:
949:
946:
943:
940:
920:
917:
914:
911:
891:
887:
883:
875:
871:
861:
859:
854:
850:
848:
844:
842:
838:
834:
832:
827:
823:
814:
812:
808:
803:
779:
776:
766:
762:
758:
753:
749:
717:
713:
709:
704:
700:
696:
693:
690:
685:
681:
677:
672:
668:
664:
659:
655:
651:
648:
645:
640:
636:
622:
614:
608:
605:
602:
593:
587:
546:
543:
521:
518:
508:
497:
489:
485:
481:
478:
475:
472:
463:
455:
451:
447:
442:
438:
407:
404:
379:
373:
370:
367:
361:
356:
352:
326:
320:
317:
314:
308:
303:
299:
271:
268:
224:
221:
218:
210:
191:
188:
175:
172:
158:
144:
140:
136:
113:
110:
107:
103:
99:
76:
73:
70:
67:
47:
43:
39:
30:
26:
24:
19:
16353:
16349:
16343:
16316:
16306:
16297:
16287:
16257:(1): 51–56.
16254:
16250:
16237:
16196:
16192:
16179:
16136:
16132:
16126:
16099:
16045:
16003:
15999:
15993:
15966:
15953:
15928:
15924:
15918:
15893:
15889:
15883:
15838:
15832:
15795:
15789:
15762:
15756:
15739:
15735:
15729:
15692:
15665:
15659:
15642:
15638:
15632:
15615:
15611:
15604:
15587:
15583:
15577:
15542:
15536:
15511:
15505:
15496:
15469:
15441:
15437:
15431:
15414:
15410:
15378:
15374:
15348:
15344:
15300:
15296:
15258:
15254:
15224:
15220:
15210:
15175:
15171:
15144:
15125:
15121:
15081:
15077:
15027:
15023:
15017:
14856:
14661:
14565:
14436:
14364:
14361:
14353:
14340:Jansen, Rau
14291:Jansen, Rau
13958:
13873:
13640:
13302:
13301:
13298:
12634:
12633:
11930:
11929:
11356:
11355:
11326:
11029:
10719:
10527:
10430:
10386:
10335:
10291:
10188:
10145:
9935:
9848:
9656:
9531:
9008:
9005:end function
9004:
9001:
8996:
8993:
8989:
8985:
8982:
8978:
8975:
8971:
8967:
8966:I not empty
8963:
8958:
8955:
8945:
8942:
8939:
8935:
8916:, its width
8899:
8795:
8471:
8133:
7680:
7129:, such that
6960:Determinate
6911:
5947:
5943:
5473:
5414:
5411:
5316:
4619:
4518:
4515:
3879:Schiermeyer
3738:Up-Down (UD)
3052:
2846:
2691:
2580:
2577:
2163:
1811:
1646:
1377:
1302:
1208:
1149:
1068:
867:
852:
851:
846:
845:
836:
835:
830:
825:
824:
820:
804:
291:has a width
208:
165:An instance
164:
31:
27:
22:
17:
15:
15178:: 120–140.
15156:. 10820228.
13617:and height
13303:Procedure 4
12970:as well as
12635:Procedure 3
12583:and height
11931:Procedure 2
11893:and height
11582:with width
11452:with width
11357:Procedure 1
10764:and height
9849:first level
8930:s.itemWidth
8914:s.yposition
8910:s.xposition
8013:such that
6806:such that
4428:Sviridenko
3837:Reverse-Fit
2824:and height
1866:and define
1503:. For each
16384:Categories
16154:2142/74223
16055:cs/0607046
15848:1610.04430
15675:2402.16572
15185:1705.04587
15009:References
13443:such that
13191:and width
13144:and width
11779:and width
9441:such that
9286:such that
6302:such that
5843:such that
5793:For every
3928:Steinberg
853:Structure:
837:Dimension:
161:Definition
16370:0377-2217
16335:0304-3975
16271:0167-6377
16221:1099-1425
16163:1432-0525
16020:1573-2886
15945:0020-0190
15910:0097-5397
15381:: 37–40.
15275:1091-9856
15227:: 56–64.
15086:CiteSeerX
15044:0377-2217
14923:Johannes
14780:ε
14740:≈
14689:≤
14610:∞
14607:→
14548:≤
14323:ε
14274:ε
14222:ε
14173:ε
14124:ε
13985:ε
13935:
13828:≤
13733:
13724:
13683:
13593:−
13505:−
13475:≥
13424:∈
13390:≤
13336:≤
13271:∖
13202:−
13003:≤
12941:≤
12906:≤
12889:−
12722:≤
12668:≤
12530:−
12381:−
12372:≤
12332:−
12305:−
12241:≥
12193:≥
12150:≥
12102:≥
12063:∈
12018:≤
11964:≤
11904:−
11871:−
11757:−
11608:−
11563:∈
11472:≥
11433:∈
11395:≥
11338:×
11245:−
11200:−
11168:−
11162:⋅
11156:≤
11106:≤
11060:≤
10982:∈
10975:∑
10674:≤
10311:≤
10261:. Define
9543:∈
9480:ε
9477:−
9373:ε
9325:ε
9322:−
9244:ε
9196:≤
9155:≤
8699:≤
8650:≤
8514:
8086:ε
8083:−
7971:ε
7963:For each
7894:≤
7756:≤
7320:≤
7180:∈
6971:∈
6861:ε
6858:−
6764:ε
6692:≤
6593:ε
6590:−
6490:ε
6408:≤
6356:∈
6345:for each
6322:≤
6243:≥
6141:≤
6100:≤
5893:ε
5890:−
5801:ε
5702:≤
5661:≤
5516:
5380:ε
5300:ε
5192:∈
5189:ε
5181:For each
5166:δ
5163:−
5073:δ
5050:δ
5047:−
4957:δ
4931:≤
4867:≤
4550:∈
4462:ε
4392:ε
4381:ε
4367:
4327:ε
4265:ε
4254:ε
4240:
4200:ε
4117:ε
4000:ε
3954:ε
3552:≤
3383:≤
3290:≤
3146:ε
2991:, where
2966:−
2925:−
2860:≥
2749:≥
2703:≥
2606:≤
2558:∈
2547:for each
2493:, where
2430:−
2416:α
2396:∈
2389:∑
2385:−
2355:α
2335:∈
2328:∑
2297:α
2277:∪
2271:α
2251:∈
2244:∑
2226:∩
2200:∈
2197:α
2189:≥
2146:α
2128:≥
2102:∈
2087:α
2021:≥
2018:α
2015:−
1997:∈
1982:α
1942:α
1939:−
1906:∈
1891:α
1849:∩
1823:∈
1820:α
1750:∑
1731:∧
1672:≥
1588:∑
1549:≤
1485:≤
1453:∑
1402:
1328:≥
1255:∈
1248:∑
1175:≥
1125:∈
847:Rotation:
826:Geometry:
780:∈
623:×
615:∈
547:∈
519:≥
509:×
498:∩
482:−
464:∈
408:∈
380:∩
362:∈
327:∩
309:∈
272:∈
114:ε
16279:15561044
16229:18819458
16171:21170278
16028:37635252
15875:15768136
15721:24303167
15202:67168004
14879:Comment
14092:Comment
13280:′
13241:′
13094:′
12932:′
12819:′
12564:′
12476:′
12415:′
12362:′
12345:′
12234:′
12143:′
12059:′
11388:′
11270:, where
10478:. Place
10465:′
10370:′
10248:′
10223:′
9365:For any
9236:For any
8936:function
8736:, where
7677:as well.
7568:of with
7016:or less.
6178:, where
5739:, where
5065:For any
4949:For any
4731:, where
3587:Sleator
864:Hardness
817:Variants
15824:3205478
15547:Bibcode
15528:5361969
14837:1.58889
14815:6.6623
14802:6.6623
14722:Source
14354:In the
14046:unless
10936:and by
10620:levels.
8956:output:
8946:items
8926:s.lower
8922:s.upper
8918:s.width
7019:Divide
6040:levels.
3179:Source
1529:define
904:unless
207:of the
60:unless
16368:
16333:
16277:
16269:
16227:
16219:
16169:
16161:
16114:
16080:
16070:
16026:
16018:
15981:
15943:
15908:
15873:
15863:
15822:
15812:
15777:
15719:
15709:
15565:
15526:
15484:
15273:
15200:
15088:
15042:
14997:2.618
14972:1.5404
14950:2.457
14876:Source
14437:where
14089:Source
11121:, and
10433:shift
10338:shift
9002:return
8943:input:
7358:Order
7254:while
6532:with
4059:1.9396
3637:Golan
2738:and a
2062:, and
1059:W-hard
21:as an
16275:S2CID
16247:(PDF)
16225:S2CID
16189:(PDF)
16167:S2CID
16078:S2CID
16050:arXiv
16024:S2CID
15963:(PDF)
15871:S2CID
15843:arXiv
15820:S2CID
15717:S2CID
15670:arXiv
15524:S2CID
15198:S2CID
15180:arXiv
15154:(PDF)
14994:2016
14960:2012
14947:2009
14934:2.43
14931:2007
14918:2.25
14915:2006
14884:1982
14825:2007
14812:2009
14799:2007
14762:1997
14730:6.99
14727:1983
14521:with
14296:2019
14247:2017
14195:2016
14146:2016
14097:2010
12444:Find
12082:with
8964:while
8906:s ∈ S
8468:left.
4306:2012
4179:2011
4047:2009
3933:2000
3592:1981
3234:1980
16366:ISSN
16331:ISSN
16267:ISSN
16217:ISSN
16159:ISSN
16112:ISBN
16068:ISBN
16016:ISSN
15979:ISBN
15941:ISSN
15906:ISSN
15861:ISBN
15810:ISBN
15775:ISBN
15707:ISBN
15563:ISBN
15482:ISBN
15271:ISSN
15040:ISSN
14867:Year
14774:1.69
14713:Year
14083:Year
13029:Set
12770:>
12464:and
12264:and
11602:>
10431:then
10406:>
10336:then
10236:and
10189:then
10165:<
10020:and
9854:Let
9468:>
9402:>
9391:and
9376:>
9313:>
9247:>
8994:else
8983:then
8924:and
8912:and
8440:and
8331:Let
8040:>
7974:>
7398:and
7219:>
7083:and
6839:>
6767:>
6565:>
6493:>
6232:Let
5881:>
5804:>
5415:Let
5365:>
5285:>
5157:>
5076:>
5041:>
4960:>
4716:>
4635:>
4519:Let
4433:2014
4096:2009
3884:1997
3834:1994
3735:1981
3489:1980
3184:1980
3173:Name
3170:Year
3081:and
2143:>
2036:>
1933:>
1791:>
1725:>
1629:>
1514:>
1029:and
809:and
697:<
691:<
652:<
646:<
16:The
16358:doi
16354:250
16321:doi
16259:doi
16209:hdl
16201:doi
16149:hdl
16141:doi
16104:doi
16082:580
16060:doi
16008:doi
15971:doi
15933:doi
15898:doi
15853:doi
15800:doi
15767:doi
15744:doi
15697:doi
15647:doi
15643:112
15620:doi
15592:doi
15555:doi
15516:doi
15474:doi
15446:doi
15419:doi
15383:doi
15353:doi
15305:doi
15263:doi
15229:doi
15225:661
15190:doi
15130:doi
15096:doi
15032:doi
15028:183
14743:1.7
14675:max
14573:lim
14534:max
13932:log
13730:log
13721:log
13680:log
13372:max
13318:max
13050:max
12704:max
12650:max
12533:max
12384:max
12000:max
11946:max
11802:If
11688:If
11372:max
11297:max
11227:max
11182:max
11088:max
11042:max
10885:max
10821:max
10101:max
9907:max
9803:max
9191:max
8749:max
8702:2.5
8686:max
8511:log
8413:at
7947:max
7827:max
6742:max
6468:max
6191:max
6144:2.7
6136:max
6103:1.7
5752:max
5697:max
5513:log
5317:not
4403:max
4364:log
4276:max
4237:log
4149:max
4017:max
3804:max
3708:max
3555:2.5
3530:max
3462:max
3430:1.5
3386:2.7
3369:max
3340:1.7
3276:max
3018:max
2952:max
2907:max
2844:if
2757:max
2711:max
2623:max
2612:max
2520:max
2193:max
1957:,
1675:max
1440:max
1399:log
1183:max
1099:max
1082:max
811:FPT
743:max
16386::
16364:.
16352:.
16329:.
16315:.
16296:.
16273:.
16265:.
16255:36
16253:.
16249:.
16223:.
16215:.
16207:.
16195:.
16191:.
16165:.
16157:.
16147:.
16137:18
16135:.
16110:.
16090:^
16076:.
16066:.
16058:.
16036:^
16022:.
16014:.
16004:17
16002:.
15977:.
15965:.
15939:.
15929:63
15927:.
15904:.
15894:12
15892:.
15869:.
15859:.
15851:.
15818:.
15808:.
15773:.
15740:39
15738:.
15715:.
15705:.
15683:^
15668:,
15641:.
15616:03
15614:.
15586:.
15561:.
15553:.
15522:.
15512:25
15510:.
15480:.
15458:^
15440:.
15415:10
15413:.
15395:^
15379:10
15377:.
15365:^
15347:.
15317:^
15301:26
15299:.
15283:^
15269:.
15259:15
15257:.
15243:^
15223:.
15219:.
15196:.
15188:.
15176:64
15174:.
15162:^
15126:47
15124:.
15120:.
15108:^
15094:.
15080:.
15052:^
15038:.
15026:.
14704:.
14659:.
14434:,
13956:.
13531:.
13359:,
13047::=
12745:,
12691:,
12440:.
12216:,
12173:,
12125:,
11987:,
11418:.
11324:,
11294::=
11075:,
10971::=
10872:,
10387:If
10292:If
10146:If
10098::=
9654:.
8979:if
8968:do
8940:is
8932:.
8902:S
5294:11
5290:12
3698:18
3161:.
3045:.
3015::=
2575:.
2517::=
2093::=
1988::=
1897::=
1809:.
1437::=
1375:.
1244::=
1206:.
1096::=
860:.
833:.
157:.
16372:.
16360::
16337:.
16323::
16300:.
16281:.
16261::
16231:.
16211::
16203::
16197:9
16173:.
16151::
16143::
16120:.
16106::
16084:.
16062::
16052::
16030:.
16010::
15987:.
15973::
15947:.
15935::
15912:.
15900::
15877:.
15855::
15845::
15826:.
15802::
15783:.
15769::
15750:.
15746::
15723:.
15699::
15672::
15653:.
15649::
15626:.
15622::
15598:.
15594::
15588:6
15571:.
15557::
15549::
15530:.
15518::
15490:.
15476::
15452:.
15448::
15442:2
15425:.
15421::
15389:.
15385::
15359:.
15355::
15349:9
15311:.
15307::
15277:.
15265::
15237:.
15231::
15204:.
15192::
15182::
15138:.
15132::
15102:.
15098::
15082:9
15046:.
15034::
14894:2
14777:+
14692:1
14686:)
14683:I
14680:(
14671:h
14647:)
14644:I
14641:(
14638:T
14635:P
14632:O
14628:/
14624:)
14621:I
14618:(
14615:A
14604:)
14601:I
14598:(
14595:T
14592:P
14589:O
14584:p
14581:u
14578:s
14551:1
14545:)
14542:I
14539:(
14530:h
14509:I
14489:)
14486:I
14483:(
14480:T
14477:P
14474:O
14454:)
14451:I
14448:(
14445:A
14422:)
14419:I
14416:(
14413:T
14410:P
14407:O
14403:/
14399:)
14396:I
14393:(
14390:A
14385:I
14380:p
14377:u
14374:s
14326:)
14320:+
14317:4
14313:/
14309:5
14306:(
14277:)
14271:+
14268:3
14264:/
14260:4
14257:(
14225:)
14219:+
14216:3
14212:/
14208:4
14205:(
14176:)
14170:+
14167:5
14163:/
14159:7
14156:(
14127:)
14121:+
14118:2
14114:/
14110:3
14107:(
14063:P
14060:N
14057:=
14054:P
14034:4
14030:/
14026:5
14006:)
14003:I
14000:(
13997:T
13994:P
13991:O
13988:)
13982:+
13979:4
13975:/
13971:5
13968:(
13944:)
13941:W
13938:(
13911:W
13890:2
13886:/
13882:3
13865:.
13853:)
13848:I
13843:(
13840:T
13837:P
13834:O
13831:2
13825:)
13820:I
13815:(
13812:T
13809:S
13787:I
13774:.
13762:)
13759:)
13756:)
13752:|
13746:I
13740:|
13736:(
13727:(
13717:/
13711:2
13707:)
13702:|
13696:I
13690:|
13686:(
13676:|
13670:I
13664:|
13660:(
13655:O
13625:H
13605:)
13602:i
13599:(
13596:w
13590:W
13579:.
13565:I
13543:i
13519:4
13515:/
13511:H
13508:W
13502:)
13497:I
13492:(
13488:A
13485:E
13482:R
13479:A
13472:)
13469:i
13466:(
13463:h
13460:)
13457:i
13454:(
13451:w
13429:I
13421:i
13401:2
13397:/
13393:H
13387:)
13382:I
13377:(
13368:h
13347:2
13343:/
13339:W
13333:)
13328:I
13323:(
13314:w
13277:I
13266:I
13238:I
13224:.
13210:1
13206:W
13199:W
13179:H
13157:1
13153:W
13132:H
13121:.
13108:H
13104:/
13100:)
13091:I
13085:(
13081:A
13078:E
13075:R
13072:A
13068:2
13065:,
13062:2
13058:/
13054:W
13042:1
13038:W
13014:4
13010:/
13006:W
13000:)
12995:1
12992:+
12989:m
12985:i
12981:(
12978:w
12958:8
12954:/
12950:H
12947:W
12944:3
12938:)
12929:I
12923:(
12919:A
12916:E
12913:R
12910:A
12903:4
12899:/
12895:H
12892:W
12886:)
12881:I
12876:(
12872:A
12869:E
12866:R
12863:A
12842:m
12816:I
12793:m
12773:1
12766:|
12760:I
12754:|
12733:2
12729:/
12725:H
12719:)
12714:I
12709:(
12700:h
12679:2
12675:/
12671:W
12665:)
12660:I
12655:(
12646:w
12616:I
12603:.
12591:H
12571:}
12568:)
12561:i
12557:(
12554:w
12551:,
12548:)
12545:i
12542:(
12539:w
12536:{
12527:W
12513:.
12499:I
12473:i
12452:i
12428:H
12425:)
12422:}
12419:)
12412:i
12408:(
12405:w
12402:,
12399:)
12396:i
12393:(
12390:w
12387:{
12378:W
12375:(
12369:)
12366:)
12359:i
12355:(
12352:h
12349:)
12342:i
12338:(
12335:w
12329:)
12326:i
12323:(
12320:h
12317:)
12314:i
12311:(
12308:w
12302:)
12297:I
12292:(
12288:A
12285:E
12282:R
12279:A
12275:(
12272:2
12252:4
12248:/
12244:H
12238:)
12231:i
12227:(
12224:h
12204:4
12200:/
12196:H
12190:)
12187:i
12184:(
12181:h
12161:4
12157:/
12153:W
12147:)
12140:i
12136:(
12133:w
12113:4
12109:/
12105:W
12099:)
12096:i
12093:(
12090:w
12068:I
12056:i
12052:,
12049:i
12029:2
12025:/
12021:H
12015:)
12010:I
12005:(
11996:h
11975:2
11971:/
11967:W
11961:)
11956:I
11951:(
11942:w
11912:0
11908:h
11901:H
11879:0
11875:w
11868:W
11846:0
11842:w
11819:H
11813:I
11787:W
11765:0
11761:h
11754:H
11732:0
11728:h
11705:H
11699:I
11685:.
11671:H
11665:I
11640:I
11616:0
11612:h
11605:H
11599:)
11596:i
11593:(
11590:h
11568:I
11560:i
11535:0
11531:h
11519:.
11505:I
11483:2
11479:/
11475:W
11469:)
11466:i
11463:(
11460:w
11438:I
11430:i
11406:2
11402:/
11398:W
11392:)
11383:I
11377:(
11368:w
11341:H
11335:W
11312:}
11309:a
11306:,
11303:0
11300:{
11289:+
11285:)
11281:a
11278:(
11256:+
11252:)
11248:W
11242:)
11237:I
11232:(
11223:w
11219:2
11216:(
11211:+
11207:)
11203:h
11197:)
11192:I
11187:(
11178:h
11174:2
11171:(
11165:H
11159:W
11153:)
11148:I
11143:(
11139:A
11136:E
11133:R
11130:A
11109:W
11103:)
11098:I
11093:(
11084:w
11063:H
11057:)
11052:I
11047:(
11038:h
11015:)
11012:i
11009:(
11006:h
11003:)
11000:i
10997:(
10994:w
10987:I
10979:i
10968:)
10963:I
10958:(
10954:A
10951:E
10948:R
10945:A
10922:I
10900:)
10895:I
10890:(
10881:w
10858:I
10836:)
10831:I
10826:(
10817:h
10794:I
10772:H
10752:W
10730:I
10711:.
10699:)
10694:I
10689:(
10686:T
10683:P
10680:O
10677:2
10671:)
10666:I
10661:(
10658:F
10655:R
10633:I
10607:|
10601:I
10595:|
10574:)
10569:2
10564:|
10557:I
10551:|
10547:(
10542:O
10524:.
10512:s
10486:s
10462:s
10441:s
10418:)
10415:s
10412:(
10409:h
10401:2
10397:h
10383:.
10367:s
10346:s
10323:)
10320:s
10317:(
10314:h
10306:2
10302:h
10274:2
10270:h
10245:s
10220:f
10198:s
10176:2
10172:/
10168:W
10160:r
10156:x
10142:.
10130:)
10125:s
10121:b
10117:,
10112:f
10108:b
10104:(
10093:r
10089:x
10068:s
10048:f
10028:s
10008:f
9986:1
9982:H
9970:.
9958:2
9954:/
9950:W
9938:.
9920:1
9916:h
9912:+
9903:h
9899:+
9894:0
9890:H
9867:1
9863:h
9851:.
9833:0
9829:H
9799:h
9787:.
9773:0
9769:H
9746:0
9742:H
9721:2
9717:/
9713:W
9689:W
9667:I
9642:)
9637:i
9633:d
9629:,
9624:i
9620:b
9616:(
9596:)
9591:i
9587:c
9583:,
9578:i
9574:a
9570:(
9548:I
9540:i
9523:.
9511:C
9508:+
9505:)
9500:I
9495:(
9492:T
9489:P
9486:O
9483:)
9474:2
9471:(
9465:)
9460:I
9455:(
9452:P
9449:S
9427:I
9405:0
9399:C
9379:0
9362:.
9350:)
9345:I
9340:(
9337:T
9334:P
9331:O
9328:)
9319:3
9316:(
9310:)
9305:I
9300:(
9297:P
9294:S
9272:I
9250:0
9233:.
9221:)
9216:I
9211:(
9208:T
9205:P
9202:O
9199:3
9187:h
9183:+
9180:)
9175:I
9170:(
9167:T
9164:P
9161:O
9158:2
9152:)
9147:I
9142:(
9139:P
9136:S
9114:I
9101:.
9088:|
9082:I
9076:|
9055:)
9050:2
9045:|
9038:I
9032:|
9028:(
9023:O
8952:W
8948:I
8885:i
8865:i
8845:j
8825:j
8805:i
8787:.
8773:I
8745:h
8724:)
8719:I
8714:(
8711:T
8708:P
8705:O
8696:2
8692:/
8682:h
8678:+
8675:)
8670:I
8665:(
8662:T
8659:P
8656:O
8653:2
8647:)
8642:I
8637:(
8634:A
8612:I
8599:.
8587:)
8583:|
8577:I
8571:|
8567:(
8562:O
8540:)
8537:)
8533:|
8527:I
8521:|
8517:(
8507:|
8501:I
8495:|
8491:(
8486:O
8453:r
8449:h
8426:l
8422:h
8401:2
8397:/
8393:W
8371:r
8367:h
8344:l
8340:h
8316:2
8312:/
8308:W
8283:0
8279:h
8264:.
8250:0
8246:h
8223:0
8219:h
8198:2
8194:/
8190:W
8166:W
8144:I
8125:.
8113:)
8108:I
8103:(
8100:T
8097:P
8094:O
8090:)
8080:)
8077:1
8074:+
8071:m
8068:(
8064:/
8060:)
8057:2
8054:+
8051:m
8048:(
8044:(
8037:)
8032:I
8027:(
8024:F
8021:S
7999:I
7977:0
7943:h
7939:2
7936:+
7933:)
7928:I
7923:(
7920:T
7917:P
7914:O
7911:)
7908:2
7904:/
7900:3
7897:(
7891:)
7886:I
7881:(
7878:F
7875:S
7855:1
7852:=
7849:m
7823:h
7819:2
7816:+
7813:)
7808:I
7803:(
7800:T
7797:P
7794:O
7791:)
7788:1
7785:+
7782:m
7779:(
7775:/
7771:)
7768:2
7765:+
7762:m
7759:(
7753:)
7748:I
7743:(
7740:F
7737:S
7717:m
7695:I
7665:R
7643:w
7640:o
7637:r
7634:r
7631:a
7628:n
7622:I
7596:)
7593:2
7590:+
7587:m
7584:(
7580:/
7576:W
7556:R
7533:)
7530:2
7527:+
7524:m
7521:(
7517:/
7513:)
7510:1
7507:+
7504:m
7501:(
7498:W
7473:e
7470:d
7467:i
7464:w
7458:I
7430:w
7427:o
7424:r
7421:r
7418:a
7415:n
7409:I
7384:e
7381:d
7378:i
7375:w
7369:I
7355:.
7343:)
7340:1
7337:+
7334:m
7331:(
7327:/
7323:W
7317:)
7314:i
7311:(
7308:w
7286:w
7283:o
7280:r
7277:r
7274:a
7271:n
7265:I
7242:)
7239:1
7236:+
7233:m
7230:(
7226:/
7222:W
7216:)
7213:i
7210:(
7207:w
7185:I
7177:i
7155:e
7152:d
7149:i
7146:w
7140:I
7115:w
7112:o
7109:r
7106:r
7103:a
7100:n
7094:I
7069:e
7066:d
7063:i
7060:w
7054:I
7029:I
7004:m
7000:/
6996:W
6975:N
6968:m
6944:W
6922:I
6900:.
6888:)
6883:I
6878:(
6875:T
6872:P
6869:O
6865:)
6855:2
6851:/
6847:3
6843:(
6836:)
6831:I
6826:(
6823:H
6820:D
6817:F
6814:F
6792:I
6770:0
6738:h
6734:+
6731:)
6726:I
6721:(
6718:T
6715:P
6712:O
6709:)
6706:2
6702:/
6698:3
6695:(
6689:)
6684:I
6679:(
6676:H
6673:D
6670:F
6667:F
6645:I
6632:.
6620:)
6615:I
6610:(
6607:T
6604:P
6601:O
6597:)
6587:m
6583:/
6579:1
6576:+
6573:1
6569:(
6562:)
6557:I
6552:(
6549:H
6546:D
6543:F
6540:F
6518:I
6496:0
6464:h
6460:+
6457:)
6452:I
6447:(
6444:T
6441:P
6438:O
6434:)
6430:m
6426:/
6422:1
6419:+
6416:1
6412:(
6405:)
6400:I
6395:(
6392:H
6389:D
6386:F
6383:F
6361:I
6353:i
6333:m
6329:/
6325:W
6319:)
6316:i
6313:(
6310:w
6290:W
6268:I
6246:2
6240:m
6229:.
6215:I
6187:h
6166:)
6161:I
6156:(
6153:T
6150:P
6147:O
6132:h
6128:+
6125:)
6120:I
6115:(
6112:T
6109:P
6106:O
6097:)
6092:I
6087:(
6084:H
6081:D
6078:F
6075:F
6053:I
6027:|
6021:I
6015:|
5994:)
5989:2
5984:|
5977:I
5971:|
5967:(
5962:O
5921:.
5918:)
5913:I
5908:(
5905:T
5902:P
5899:O
5896:)
5887:2
5884:(
5878:)
5874:|
5868:I
5863:(
5860:H
5857:D
5854:F
5851:N
5829:I
5807:0
5790:.
5776:I
5748:h
5727:)
5722:I
5717:(
5714:T
5711:P
5708:O
5705:3
5693:h
5689:+
5686:)
5681:I
5676:(
5673:T
5670:P
5667:O
5664:2
5658:)
5653:I
5648:(
5645:H
5642:D
5639:F
5636:N
5614:I
5601:.
5589:)
5585:|
5579:I
5573:|
5569:(
5564:O
5542:)
5539:)
5535:|
5529:I
5523:|
5519:(
5509:|
5503:I
5497:|
5493:(
5488:O
5459:)
5456:0
5453:,
5450:0
5447:(
5425:I
5395:.
5377:+
5374:3
5370:4
5362:)
5359:L
5356:(
5353:T
5350:P
5347:O
5343:/
5339:)
5336:L
5333:(
5330:L
5327:B
5297:+
5282:)
5279:L
5276:(
5273:T
5270:P
5267:O
5263:/
5259:)
5256:L
5253:(
5250:L
5247:B
5227:L
5207:]
5204:1
5201:,
5198:0
5195:(
5178:.
5160:2
5154:)
5151:L
5148:(
5145:T
5142:P
5139:O
5135:/
5131:)
5128:L
5125:(
5122:L
5119:B
5099:L
5079:0
5062:.
5044:3
5038:)
5035:L
5032:(
5029:T
5026:P
5023:O
5019:/
5015:)
5012:L
5009:(
5006:L
5003:B
4983:L
4963:0
4946:.
4934:2
4928:)
4925:L
4922:(
4919:T
4916:P
4913:O
4909:/
4905:)
4902:L
4899:(
4896:L
4893:B
4882:.
4870:3
4864:)
4861:L
4858:(
4855:T
4852:P
4849:O
4845:/
4841:)
4838:L
4835:(
4832:L
4829:B
4818:.
4806:L
4786:)
4783:L
4780:(
4777:T
4774:P
4771:O
4751:)
4748:L
4745:(
4742:L
4739:B
4719:M
4713:)
4710:L
4707:(
4704:T
4701:P
4698:O
4694:/
4690:)
4687:L
4684:(
4681:L
4678:B
4658:L
4638:0
4632:M
4605:)
4602:y
4599:,
4596:x
4593:(
4573:r
4553:L
4547:r
4527:L
4483:)
4480:I
4477:(
4474:T
4471:P
4468:O
4465:)
4459:+
4456:3
4452:/
4448:5
4445:(
4414:)
4411:I
4408:(
4399:h
4395:)
4388:/
4384:)
4377:/
4373:1
4370:(
4361:(
4356:O
4351:+
4348:)
4345:I
4342:(
4339:T
4336:P
4333:O
4330:)
4324:+
4321:1
4318:(
4287:)
4284:I
4281:(
4272:h
4268:)
4261:/
4257:)
4250:/
4246:1
4243:(
4234:(
4229:O
4224:+
4221:)
4218:I
4215:(
4212:T
4209:P
4206:O
4203:)
4197:+
4194:1
4191:(
4160:)
4157:I
4154:(
4145:h
4141:+
4138:)
4135:I
4132:(
4129:T
4126:P
4123:O
4120:)
4114:+
4111:1
4108:(
4077:)
4074:I
4071:(
4068:T
4065:P
4062:O
4028:)
4025:I
4022:(
4013:h
4009:)
4004:2
3995:/
3991:1
3988:(
3983:O
3978:+
3975:)
3972:I
3969:(
3966:T
3963:P
3960:O
3957:)
3951:+
3948:1
3945:(
3914:)
3911:I
3908:(
3905:T
3902:P
3899:O
3896:2
3865:)
3862:I
3859:(
3856:T
3853:P
3850:O
3847:2
3815:)
3812:I
3809:(
3800:h
3794:8
3791:7
3786:6
3783:+
3780:)
3777:I
3774:(
3771:T
3768:P
3765:O
3762:)
3759:4
3755:/
3751:5
3748:(
3719:)
3716:I
3713:(
3704:h
3695:1
3690:7
3687:+
3684:)
3681:I
3678:(
3675:T
3672:P
3669:O
3666:)
3663:3
3659:/
3655:4
3652:(
3623:)
3620:I
3617:(
3614:T
3611:P
3608:O
3605:3
3573:)
3570:I
3567:(
3564:T
3561:P
3558:O
3549:2
3545:/
3541:)
3538:I
3535:(
3526:h
3522:+
3519:)
3516:I
3513:(
3510:T
3507:P
3504:O
3501:2
3473:)
3470:I
3467:(
3458:h
3454:2
3451:+
3448:)
3445:I
3442:(
3439:T
3436:P
3433:O
3404:)
3401:I
3398:(
3395:T
3392:P
3389:O
3380:)
3377:I
3374:(
3365:h
3361:+
3358:)
3355:I
3352:(
3349:T
3346:P
3343:O
3311:)
3308:I
3305:(
3302:T
3299:P
3296:O
3293:3
3287:)
3284:I
3281:(
3272:h
3268:+
3265:)
3262:I
3259:(
3256:T
3253:P
3250:O
3247:2
3215:)
3212:I
3209:(
3206:T
3203:P
3200:O
3197:3
3149:)
3143:+
3140:3
3136:/
3132:5
3129:(
3109:2
3089:2
3069:3
3033:}
3030:0
3027:,
3024:x
3021:{
3010:+
3006:)
3002:x
2999:(
2977:+
2973:)
2969:H
2963:)
2960:I
2957:(
2948:h
2944:2
2941:(
2936:+
2932:)
2928:W
2922:)
2917:I
2912:(
2903:w
2899:2
2896:(
2893:+
2890:)
2885:I
2880:(
2876:A
2873:E
2870:R
2867:A
2863:2
2857:H
2854:W
2832:H
2812:W
2790:I
2768:)
2765:I
2762:(
2753:h
2746:H
2726:)
2721:I
2716:(
2707:w
2700:W
2678:.
2675:}
2672:W
2668:/
2664:)
2659:I
2654:(
2650:A
2647:E
2644:R
2641:A
2637:,
2634:)
2631:I
2628:(
2619:h
2615:{
2609:2
2603:)
2600:I
2597:(
2594:T
2591:P
2588:O
2562:R
2555:x
2535:}
2532:0
2529:,
2526:x
2523:{
2512:+
2508:)
2504:x
2501:(
2479:}
2472:+
2467:)
2462:W
2457:)
2454:i
2451:(
2448:h
2445:)
2442:)
2439:i
2436:(
2433:w
2427:W
2424:(
2419:)
2413:(
2408:2
2402:I
2393:i
2382:)
2379:i
2376:(
2373:w
2370:)
2367:i
2364:(
2361:h
2358:)
2352:(
2347:3
2341:I
2332:i
2322:(
2317:+
2314:)
2311:i
2308:(
2305:h
2300:)
2294:(
2289:2
2283:I
2274:)
2268:(
2263:1
2257:I
2248:i
2238:{
2230:N
2223:]
2220:2
2216:/
2212:W
2209:,
2206:1
2203:[
2186:)
2183:I
2180:(
2177:T
2174:P
2171:O
2149:}
2140:)
2137:i
2134:(
2131:w
2125:2
2121:/
2117:W
2113:|
2107:I
2099:i
2096:{
2090:)
2084:(
2079:3
2073:I
2050:}
2047:2
2043:/
2039:W
2033:)
2030:i
2027:(
2024:w
2012:W
2008:|
2002:I
1994:i
1991:{
1985:)
1979:(
1974:2
1968:I
1945:}
1936:W
1930:)
1927:i
1924:(
1921:w
1917:|
1911:I
1903:i
1900:{
1894:)
1888:(
1883:1
1877:I
1853:N
1846:]
1843:2
1839:/
1835:W
1832:,
1829:1
1826:[
1797:}
1794:W
1788:)
1785:j
1782:(
1779:w
1774:)
1771:l
1768:(
1765:i
1760:1
1757:=
1754:j
1746:+
1743:)
1740:l
1737:(
1734:w
1728:k
1722:l
1718:|
1714:)
1711:)
1708:l
1705:(
1702:i
1699:(
1696:h
1693:+
1690:)
1687:l
1684:(
1681:h
1678:{
1669:)
1666:I
1663:(
1660:T
1657:P
1654:O
1632:W
1626:)
1623:j
1620:(
1617:w
1612:)
1609:l
1606:(
1603:i
1598:1
1595:=
1592:j
1584:+
1581:)
1578:l
1575:(
1572:w
1552:k
1546:)
1543:l
1540:(
1537:i
1517:k
1511:l
1491:}
1488:W
1482:)
1479:j
1476:(
1473:w
1468:k
1463:1
1460:=
1457:j
1449::
1446:i
1443:{
1434:k
1414:)
1411:)
1408:n
1405:(
1396:n
1393:(
1388:O
1363:W
1359:/
1355:)
1350:I
1345:(
1341:A
1338:E
1335:R
1332:A
1325:)
1322:I
1319:(
1316:T
1313:P
1310:O
1288:)
1285:i
1282:(
1279:w
1276:)
1273:i
1270:(
1267:h
1260:I
1252:i
1241:)
1236:I
1231:(
1227:A
1224:E
1221:R
1218:A
1194:)
1191:I
1188:(
1179:h
1172:)
1169:I
1166:(
1163:T
1160:P
1157:O
1135:}
1130:I
1122:i
1118:|
1114:)
1111:i
1108:(
1105:h
1102:{
1093:)
1090:I
1087:(
1078:h
1045:4
1041:/
1037:5
1017:2
1013:/
1009:3
982:4
978:/
974:5
950:P
947:N
944:=
941:P
921:P
918:N
915:=
912:P
892:2
888:/
884:3
790:}
785:I
777:i
773:|
767:i
763:h
759:+
754:i
750:y
746:{
723:}
718:i
714:h
710:+
705:i
701:y
694:y
686:i
682:y
678:,
673:i
669:w
665:+
660:i
656:x
649:x
641:i
637:x
632:|
627:Q
619:Q
612:)
609:y
606:,
603:x
600:(
597:{
594:=
591:)
588:i
585:(
581:n
578:n
575:i
552:I
544:i
522:0
514:Q
506:)
502:Q
495:]
490:i
486:w
479:1
476:,
473:0
470:[
467:(
461:)
456:i
452:y
448:,
443:i
439:x
435:(
413:I
405:i
384:Q
377:]
374:1
371:,
368:0
365:(
357:i
353:h
331:Q
324:]
321:1
318:,
315:0
312:(
304:i
300:w
277:I
269:i
247:I
225:1
222:=
219:W
195:)
192:W
189:,
184:I
179:(
176:=
173:I
145:2
141:/
137:3
117:)
111:+
108:3
104:/
100:5
97:(
77:P
74:N
71:=
68:P
48:2
44:/
40:3
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
