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.