bin packing with overlapping objects I have $N$ bins with capacity $M$ and $k$ objects with size $s_i$. 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 others. So while object 1 and 2 have sizes $s_1$ and $s_2$, when I put them in the same bin the filled space will be $s_1+s_2-O_{12}$ where $O_{12}\ge0$. Note that for 3 objects it is $s_1+s_2+s_3-O_{12}-O_{23}-O_{13}+O_{123}$

Is there any approximation algorithm like the ones for original bin-packing for this problem too?
Your problem is a generalization of the sharing-aware virtual machine colocation problem, and so hard to approximate.

Read this paper for more information:
Michael Sindelar, Ramesh K. Sitaraman, Prashant J. Shenoy: Sharing-aware algorithms for virtual machine colocation. SPAA 2011: 367-378