English to Hungarian Science Science (general) ládapakoló algoritmusokról szóló cikk

A "Worst-case performance bounds for simple one-dimensional packing algorithms" c. cikk 7. oldalán van ez a mondat, az egyetemista matematikusnak tanuló fiam küldte el e-mailben, hogy ez mit jelenthet; nekem az egész szöveg abszolút ókínai, de hátha tudtok a gyerekemnek segíteni. Előre is köszönöm szépen a válaszokat, Erzsi


Let us define the coarseness of a bin to be the largest a such that some bin with smaller index is filled to level 1 — a. The coarseness of the first bin is 0.
CLAIM 2.2.2. Suppose bins are filled according to either the FF or the BF algo-rithm, and some bin B has coarseness a. Then every member of B that was placed there before B was more than half full exceeds a.
Proof. Until the bin has been filled to a level greater than it must be either empty or the unique nonempty bin of lowest level (by property (i) of the placement algorithm), so by constraints (i) and (ii), any element placed in the bin must not fit in any bin with lower index, and hence must exceed a.
CLAIM 2.2.3. Let a bin of coarseness a < | be filled with numbers b., 2; b2 in the completed FF-packing (BF-packing). If Ei"=i bt > 1 — a, then
Proof. If b, > I, then the result is immediate since Wihf = 1. We therefore assume that bt |. If m 2r 2, then the second element placed in the bin was placed before the bin was more than half full, so by Claim 2.2.2, at least two of the elements exceed a. In particular, we must have bt 2: b2 2: a.



Let us define the COARSENESS of a bin to be the largest alpha s. t. some bin etc.