Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a project concerning "on-line Batched bin Packing" where the item sizes should be between 0 and 1 and have to be packed into bins of size 1.

In my project I have to design a 3-batched online bin packing. For this version of the problem, the items to be packed arrive in at most 3 batches, and each batch contains items of only ONE size. My goal is to find goal is to find a good way to deal with the first two batches, and prove mathematically that the resulting algorithm has good performance, when compared to the optimal solution.

The second problem I am facing is to find the asymptotic competitive ratio for this kind of problem.

For example, if the input like this:

165 N * 1/1000

   N * 0.334

   N * 0.501 or N*0.51

How does it pack the first batch?

How does it pack the last batch?

What is the competitive ratio?

I will appreciated if someone can help me to find a good way to deal with this.

share|improve this question
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.