bin packing with overlapping objects

Question

I have some bins with different capacities and some objects with specified size. The goal is to pack these objects in the bins. Until now it is similar to the bin-packing problem. But the twist is that each object has a partial overlap with another. So while object 1 and 2 has sizes s1 and s2, when I put them in the same bin the filled space is less than s1+s2. Supposing that I know this overlapping value for each pair of objects, is there any approximation algorithm like the ones for original bin-packing for this problem too?

Answer 1

The answer is to use a kind of tree that captures the similarity of objects assuming that objects can be broken. Then run a greedy algorithm to fill the bins according to the tree. This algorithm has 3-x approximation bound. However, there should also be better answers.

This method is presented in Michael Sindelar, Ramesh K. Sitaraman, Prashant J. Shenoy: Sharing-aware algorithms for virtual machine colocation. SPAA 2011: 367-378.

I got this answer from this thread but just wanted to close this question by giving the answer.

Answer 2

The only algorithm I think will work is to prune items that doesn't fit into the bins and use another bin. I don't mean first fit algorithm but to wait a period of time and then use new bins for the items. In reality you can use just another bin? It's a practical approach. I mean you can grow the bin to the left or to the right like in this example: http://codeincomplete.com/posts/2011/5/7/bin_packing/.