Online Bin Packing algorithm: ration of 4/3

[zak100]

Hi,

Can somebody please explain me the following figure in the context of online bin packing algorithm:

Quote

 

Theorem 1:

There are inputs that force each online bin packing algorithm to

use at least 4/3 OPT bins where OPT is the minimum number of bins

possible.

Proof:

Assumption: online bin packing algorithm A always uses less than 4/3 OPT bins

 

I can't understand the concept related to the ration 4/3. Somebody please guide me.

 

Zulfi.

[Ghideon]

1 hour ago, zak100 said:

I can't understand the concept related to the ration 4/3. Somebody please guide me.

I assume the proof continues? Probably it uses the observation that if the online algorithm uses less than 4/3 OPT bins it must maintain that ratio at all times. A proof can use that observation and, as per the image, use two sequences of items of sizes (1/2-a) and (1/2+a) 1/2>a>0. 

[Strange]

4 hours ago, zak100 said:

Can somebody please explain me the following figure in the context of online bin packing algorithm:

Can you provide the source so we have more context

[taeto]

Knowing that algorithm A always spends less than \(4n/3\) boxes to pack items that require at most \(n\) boxes, you can think about what A must do when you feed it items one by one in the sequence shown in the figure. 

What will A do with the first two items of size \(1/2-a?\) If A places them in different boxes, then A uses 2 boxes, but obviously the optimal solution for this short sequence is 1 box. In that case A would have used 2 times as many boxes as needed, which is more than 4/3. We deduce that A must place both those items in the same box. This is still a dangerous strategy, because the third and fourth items to arrive could both be of size \(1/2+a\). Then they do not fit together in a single new box, so you have to open two new boxes to place them in. You have now spent 3 boxes on packing four items which could have been packed into 2 boxes, by fitting one small and one large item together in each of two boxes. The solution that A gets overshoots the optimal solution by a factor of 3/2 in this case, which is also more than 4/3. 

Now it seems a done deal. Whatever A does with the first four items must cause it to use at least 50% more boxes than actually needed. But there is one special thing about the analysis of approximation algorithms: you only have to consider for solution values, that is in this case the number of boxes that it uses, that are very large. Then you may consider the number of boxes that A gets forced to use versus the optimal number, now in the limit as the number \(m\) increases. At least the way to think about what A must do is similar to how to think about inputs with only a small number of items in the input sequence.  

6 hours ago, Ghideon said:

 if the online algorithm uses less than 4/3 OPT bins it must maintain that ratio at all times

That would overlook the special aspect of the analysis of approximation algorithms that the ratio is always asymptotic. You may exceed the ratio for some inputs, but only for a bounded size of the solution values.

Edited April 15, 2020 by taeto

[Ghideon]

1 hour ago, taeto said:

That would overlook the special aspect of the analysis of approximation algorithms that the ratio is always asymptotic. You may exceed the ratio for some inputs, but only for a bounded size of the solution values.

Ok. Haven't touched this topic for a long time, I don't remember limits or unbounded number of items in the proof.

edit: Checked, my book was printed in 1993,  guess I'll have to read some to catch up. 

Edited April 15, 2020 by Ghideon

[zak100]

Hi,

Thanks for your responses. I am trying to understand them.

I found the link:

 

http://ac.informatik.uni-freiburg.de/lak_teaching/ws07_08/algotheo/Slides/13_bin_packing.pdf

 

13_bin_packing.pdf

[taeto]

28 minutes ago, Ghideon said:

Ok. Haven't touched this topic for a long time

Me too. Maybe there are variations in the definitions of the competitive ratio. It just seems too easy to show a bound of 3/2 in place of 4/3 if you do not require the asymptotic limit. It is the value 4/3 which makes sense asymptotically.

Also I expressed it wrong: you can exceed the ratio 4/3 infinitely often, so long as you approach it in the limit. This has no implications for this problem, which deals with assuming an A that has ratio strictly less than 4/3. 

[Ghideon]

4 hours ago, taeto said:

Maybe there are variations in the definitions of the competitive ratio.

I found the proof i based my statement upon, it was sorted under data structures (not algorithms) for some reason. 

 

 

[taeto]

2 hours ago, Ghideon said:

I found the proof i based my statement upon, it was sorted under data structures (not algorithms) for some reason. 

It all sounds right. Which text is this from? And how is the performance guarantee defined in that text?

If we assume m = 2 in that same proof, why would it not prove that the bound is at least a factor of 3/2 by the same argument, except we replace 4/3 by 3/2. The inequality which reads 2b/m < 4/3 in that proof would then read b < 3/2. And the inequality which reads (2m - b)/m < 4/3 would read (4 - b)/2 < 3/2, that is, b > 1. Since b is an integer, this is a contradiction. 

It is the same as the mock argument which I gave above in another post.

I suspect that your recollection is top notch. However, I fear the source of your information cannot necessarily be trusted.

The paper https://arxiv.org/pdf/1807.05554.pdf gives more details on background and more recent bounds. Their new lower bound for the asymptotic competitive ratio is larger than 1.54278.

Edited April 15, 2020 by taeto

[zak100]

Hi,

Your discussion really gave me some insight. I don't know much about that. My teacher taught it several times but I can't get anything but discussion is recalling me what my teacher taught.  This is the advantage of discussion. Thanks.

Quote

What will A do with the first two items of size 1/2−a? If A places them in different boxes, then A uses 2 boxes, but obviously the optimal solution for this short sequence is 1 box. In that case A would have used 2 times as many boxes as needed, which is more than 4/3. We deduce that A must place both those items in the same box. This is still a dangerous strategy, because the third and fourth items to arrive could both be of size 1/2+a. 

This is a good strategy. According to this 'a' can be 0.4 (1/2>a>0). So 0.5-0.4 = 0.1 and two sequences of 1/2-a can easily fit in one box. But if a = 0.1 then still 1/2-,1 = 0.4, again two sequences of (1/2-a) can fit in a box because the boxes are of unit size. So what my friend "taeto" is saying is correct. 

Now:

Quote

his is still a dangerous strategy, because the third and fourth items to arrive could both be of size 1/2+a. Then they do not fit together in a single new box, so you have to open two new boxes to place them in. You have now spent 3 boxes on packing four items which could have been packed into 2 boxes, by fitting one small and one large item together in each of two boxes. 

if a=0.1 then, 0.5+1 = 0.6 so 1/2+a  items would consume 2 additional boxes, total space =  0.8 of 1st box and 1.2 of two boxes so its 1.2 +.8 = 2 boxes. But if a= 0.4 then again we would occupy 0.2 of 1st box, and 0.9 + 0.9 = 1.8 of two boxes which is again two boxes. So we can achieve the optimal solution in both the cases.  But we have to use some technique which is discussed by my friend Ghideon i.e, this actually recalled me about my professor, he discussed this solution in the context of load balancing, and he again talked about the ratio 4/3 OPT but he said that we sort the items in decreasing order of wait.

 

Our items are (1/2-a) (1/2-a), (1/2+a) and (1/2+a), let a= 0.1 then we have

0.4, 0.4, 0.6, 0.6, so if we sort in decreasing order we can do that because this he talked in the context of offline bin packing.

 

So after sorting we have, 0.6, 0.6, 0.4, 0.4,

I think we can do it in two boxes.

Now for a=0.4,

Our items are: 0.1, 0.1, 0.9, 0.9

 

we would sort in decreasing order of weight: 0.9, 0.9, 0.1, 0.1

So they would fit.

Thanks Ghideon, taeto and Strange.

 

God bless you.

Ghideon , what is the name of your book?

I can't understand the values in the time axes, what is meant by 1, 2, m, m+1, m+2, and 2m?

Somebody please guide me.

Zulfi.

[Ghideon]

 

8 hours ago, taeto said:

Which text is this from?

Good point, thanks! I forgot to post the source: Data structures and algorithm analysis in Ada, Mark Allen Weiss.

Below is the introduction to the proof. I think the text by this author has the purpose of simply discussing differences between online and offline versions of bin packing algorithms. Lower bound for the asymptotic case is not detailed. The point is to give a simple proof that offline algorithms cannot guarantee optimal solutions, hence the required details for a full understanding of the offline algorithms' best performance is missing. I also note that this book was used in the early introductions courses.

 

9 hours ago, taeto said:

The paper https://arxiv.org/pdf/1807.05554.pdf gives more details on background and more recent bounds.

Thanks! I'll read it.

 

[zak100]

Hi,

Thanks for these book images. 

Sorry I can't understand the sequences of I1 and I2.

Zulfi.

[taeto]

3 minutes ago, zak100 said:

Sorry I can't understand the sequences of I1 and I2

He is looking at the case when for a long time, you get items of the same size just less than a half, say 0.499. You keep getting those, and you have to decide how to pack some of them together into one box, because two of them will fit. Or to just leave some of them in half-packed boxes, because maybe later there will come items to fill up those boxes. 

Now in our case, the sequence I2 just means a sequence of items of size a little more than a half, at most .501. So that if you left any box ready which as only filled up to 0.499 of its capacity, then you can drop one of these items in there to fill the box. But if you do not have a box ready, then you have to open a new box to accomodate it.

[zak100]

Hi,

Thanks I understand I1 and I2.

<Or to just leave some of them in half-packed boxes, because maybe later there will come items to fill up those boxes.>

Can we do this in online?

Can we go back to previous bin?

If this is the case then online can have the same performance as optimal which is not possible.

In the attached slide, we are comparing OPT with algorithm A. OPT can require m/2 bins (why?)

They have supposed the bins required by A to b.

After that they are saying that :

b1= # of bins containing one item (i.e. each of these bins will contain large items i.e greater than 0.5 so each bin will have one item)

b2 = # of bins containing 2 items (i.e each of these bins contain 2 items such that their collective weight/space is less than 1)

Then we have

 b1 + 2b2 = m

b1 = m- 2b2

b = m -b2

 

What is the point of showing these calculations?

Thanks for helping me.

God bless you.

Zulfi.

[taeto]

13 hours ago, zak100 said:

<Or to just leave some of them in half-packed boxes, because maybe later there will come items to fill up those boxes.>

Can we do this in online?

Can we go back to previous bin?

If this is the case then online can have the same performance as optimal which is not possible.

Yes, you can choose to pack the new item in any one of the existing bins, or in a new bin. 

Once you have packed an item in a bin, you are not allowed to move it to another bin; it has to stay until the end in the bin where it was first packed. Which is why you cannot in general achieve the optimal solution.

13 hours ago, zak100 said:

In the attached slide, we are comparing OPT with algorithm A. OPT can require m/2 bins (why?)

Now I suppose that \(m\) is the number of items of size less than but close to \(1/2\). Their combined size is nearly \(m/2\), and a bin can only hold items that have sizes adding up to \(1\). Then clearly you need at least \(m/2\) bins. In fact you can get away with using exactly \(m/2\) bins, since the items can be paired off so that each pair has size less than \(1\).

13 hours ago, zak100 said:

They have supposed the bins required by A to b.

After that they are saying that :

b1= # of bins containing one item (i.e. each of these bins will contain large items i.e greater than 0.5 so each bin will have one item)

b2 = # of bins containing 2 items (i.e each of these bins contain 2 items such that their collective weight/space is less than 1)

Then we have

 b1 + 2b2 = m

b1 = m- 2b2

b = m -b2

What is the point of showing these calculations?

I read this to mean that if we observe what A is doing as it receives the initial \(m\) items each of size \(< 1/2\), we will see that \(b1\) bins are used to pack just one item in each, and \(b2\) are used to pack two items. This is different from what you are saying, since I assume that all the \(m\) initial items have size \(< 1/2\). The larger items, if any, will arrive only later.

The calculations are used to compare the number \(b\) of bins that A uses to the optimal number \(m/2\). A must use a balanced approach, that is, it has to pack a certain number of bins with two items and a certain number with only one item. Even though each bin has room for two items, it would be a mistake to pack two items into each bin, because it would make A perform poorly if and when \(m\) further items arrive each of size \(> 1/2\). It would also be a mistake to pack each bin with only a single item, since if no large items arrive (A is not allowed to know the information about the total number of items), A will have used \(m\) bins where the optimum solution is half as many, and that is bad performance.

Edited April 18, 2020 by taeto

[zak100]

Hi taeto,

You are trying too hard but still I have got confusion when I am following the book's page step by step:

Stepwise

'

Quote

A' running on the input sequence I1, Recall that this sequence consists of m small items followed by m large items.

Let m=2, then the sequence is:

0.4, 0.2, 0.6, .51

i.e. 0.2 is the mth small item and 0.51 is the mth largest item.

The book page further says:

Quote

Let us consider what the algorithm A has done after processing the mth item. Suppose A has already used b bins.

In terms of bins, is b =3?

The book page further says:

Quote

At this point in the algorithm the optimal number of of bins is m/2 because we can place 2 items in each bin.

m/2 means 1, its not possible to put 4 items in ‘1’ bin.

 

Please guide me.

Sorry I am taking your too much time.

 

Zulfi

[taeto]

5 hours ago, zak100 said:

Let m=2, then the sequence is:

0.4, 0.2, 0.6, .51

i.e. 0.2 is the mth small item and 0.51 is the mth largest item.

Hi Zulfi

Your numbers will work just as good. But for the original proof in the book the idea is that there are m small items at the beginning, all of the same size. And there are up to m larger items at the end, also all of the same size. When the sizes are chosen in addition so that one large and one small item fit together in one bin with no spare room, then we can be absolutely sure that the value of OPT is exactly m. When you choose varying sizes as you do, it becomes more tricky to check that OPT doesn't end up below m.

6 hours ago, zak100 said:

The book page further says:

In terms of bins, is b =3?

We do not know how many bins A uses among the first m. The algorithm can do whatever it wants. All we know is that A must use between m/2 and m bins to pack the first m items (if we assume that three of them will not fit into the same bin). Whichever number of bins it uses, we call that number b.

6 hours ago, zak100 said:

The book page further says:

m/2 means 1, its not possible to put 4 items in ‘1’ bin.

When it says "At this point in the algorithm" they mean: after the first m items have appeared, and we are still waiting for possibly more to arrive. At that point you have m items, any two of which fit together in a single bin. So then the optimal number of bins possible to use would be m/2, in the special case when no more items come in. Remember the algorithm does not know when the stream will stop of more items to get packed. In your example, after arrival of the two small items, the optimal way to pack just those items will require only one bin.

6 hours ago, zak100 said:

Sorry I am taking your too much time.

No problem. Pretty much stuck to this chair anyway. 

[zak100]

Hi,

Thanks. I checked it with another sequence same as what you said (0.4, 0.4, 0.4, 0.4, 0.6, 0.6, 0.6, 0.6). I found that its not possible that online can be 4/3 of optimal.

 

Zulfi.