5
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ How is the input given? There can be exponentially many O_{ijk...}'s, are these all listed? $\endgroup$
    – Mohammad
    Jul 27, 2012 at 0:13
  • $\begingroup$ Yes, Actually each item is a set of another tiny items. So s1 is the size of a set and O_{ijk...} can be computed easily. $\endgroup$
    – Masood_mj
    Jul 27, 2012 at 0:58

3 Answers 3

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

So, each object is a set and the size of a collection of objects is the size of their union, right?

I don't have a proof, but my guess is that the problem is hard/difficult. Here's why:

One special case of the problem is this: when all objects correspond to sets of size 2, then we have the following graph problem (each object corresponds to an edge of the graph): given a graph G, cover its edges with the minimum number of complete graphs of size M. The more general problem is essentially the hypergraph version of this problem.

Observation: this problem is essentially a set cover problem (with sets corresponding to M-subsets of the vertices of graphs, and covering all edges that are contained in that subset). So, the greedy algorithm that each time picks the set that covers most uncovered objects is a log(k) approximation to the optimal.

Unfortunately, this algorithm is not poly-time in general, since computing the set that covers the maximum number of uncovered objects is equivalent to the densest M-subgraph problem, which is believed to be a hard problem.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes each object is a set and the size of collection is the size of their union. So what can I say about the problem. Its NP-Hard and the log(k) approximation for that is also non-polynomial? $\endgroup$
    – Masood_mj
    Jul 27, 2012 at 5:59
1
$\begingroup$

As mentioned by snowie, your problem is a generalization of the sharing-aware virtual machine colocation problem, and is 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

The paper shows hardness for the general problem. But also provides efficient algorithms when the sharing ("overlaps") are not arbitrary but hierarchical (which is often the case with VMs.) Example of hierarchical sharing: Windows VM's share more pages with each other than Linux VMs, etc.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.