I am having a problem understanding the following:

This is the background of the lemma:

To prove the lower bounds, we use the classical lower bound construction from [5, 9]. We have an input instance L with three regions of items. In the first region, there are items of size close to 1/6, in the second region come items close to 1/3, and in the third region there are items with the equal size 1/2 + δ, for a small δ > 0. We will not modify the items in this list, only add some new items before or after L, and also in between the three regions of L. Thus we need to review the properties of L with a focus on the resulting FF packing in each region; the details within each region are somewhat delicate but fortunately we can use that part as a black box. We formulate the properties of L in the next lemma, before giving our lower bound in Theorem 4.2.

then comes the lemma

For every k and a sufficiently small δ > 0 there exists an instance L of 30k items such that Opt = 10k + 1 and FF = 17k for L. Furthermore the following holds for $ε = 46 · 18^{k−1} δ = O(δ)$:

  1. The first 10k items of L have a size of at least 1/6 − $\epsilon$ and are packed into the first 2k FF bins; no further item is packed later into these bins. Each of these 2k FF-bins is a big 5-bin, and has size at least 5/6 + δ;
  1. The next 10k items of L have size at least 1/3 − $\epsilon$ and are packed into the next 5k FF bins; no further item is packed later into these bins. Each of these FF-bins is a common 2-bin and has a size of at least 2/3 + 2δ.
  1. The last 10k items of L have a size of exactly 1/2 + δ and are packed into the next 10k FF-bins. Each of these FF bins is a dedicated bin and has a size of exactly 1/2 + δ.
  1. Moreover, all items of L, except three items, fit into 10k−1 bins, each of size $1−O(δ)$. The three remaining items have sizes 1/3 + ε, 1/6 − 3δ, and 1/2 + δ.

In the lemma, I understand points 1 to 3 but for point number 4 I have no idea. I don't understand why we have these 1/3 + ε, and 1/6 - 3δ values.

Here is the resource (you can find the lemma on page 10) https://drops.dagstuhl.de/opus/volltexte/2013/3963/pdf/51.pdf

  • 1
    $\begingroup$ Hi, sorry for the inconvenience. I already edited the question $\endgroup$ Dec 22, 2022 at 14:10
  • $\begingroup$ We prefer that you give a full citation to the source: title, authors, where published, and a link to a freely available PDF. You've gotten the last one. Could you edit your question to include the others as well? This helps ensure credit is properly given, that others can still find the paper if the link stops working, and that others with a similar question about this paper can find it via websearch. $\endgroup$
    – D.W.
    Dec 23, 2022 at 20:12


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.