In the wikipedia article on bin-packing it is stated that

A variant of bin packing that occurs in practice is when items can share space when packed into a bin. Specifically, a set of items could occupy less space when packed together than the sum of their individual sizes. This variant is known as VM packing (Sindelar et al. 2011) since when virtual machines (VMs) are packed in a server, their total memory requirement could decrease due to pages shared by the VMs that need only be stored once. If items can share space in arbitrary ways, the bin packing problem is hard to even approximate.

I checked the article of Sindelar et al., where it is in fact shown that a variant of knapsack with overlapping items (called VM-maximization if several knapsacks are allowed, however, the reduction uses only one knapsack) cannot be approximated under complexity theoretic assumptions (Theorem 3.1.3). The complexity of approximating the aforementioned bin packing variant is stated as an open problem.

Question: Is there known more about the complexity of approximating the VM Packing Problem by now?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.