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

 
discard

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

Browse other questions tagged or ask your own question.