<p>Your problem is a generalization of the sharing-aware virtual machine colocation problem, and so hard to approximate.</p>

<p>Read this paper for more information:
<a href="http://lass.cs.umass.edu/papers/pdf/SindelarSS11.pdf">Michael Sindelar, Ramesh K. Sitaraman, Prashant J. Shenoy: Sharing-aware algorithms for virtual machine colocation. SPAA 2011: 367-378</a></p>

CC BY-SA 3.0
2012-07-27T04:58:09.243Z
2012-07-27T04:58:09.243Z
Snowie
<p>As mentioned by snowie, your problem is a generalization of the sharing-aware virtual machine colocation problem, and is hard to approximate.</p>

<p>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</p>

<p>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.</p>

CC BY-SA 3.0
2012-08-01T17:23:04.617Z
2012-08-01T17:23:04.617Z
RRR
<p>So, each object is a set and the size of a collection of objects is the size of their union, right?</p>

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

<p>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. </p>

<p>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. </p>

<p>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.</p>

CC BY-SA 3.0
2012-07-27T05:59:48.033Z
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?
Masood_mj
CC BY-SA 3.0
2012-07-27T04:19:04.970Z
2012-07-27T04:19:04.970Z
Mohammad
<p>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}$</p>

<p>Is there any approximation algorithm like the ones for original bin-packing for this problem too?</p>

CC BY-SA 3.0
2012-07-27T00:13:00.753Z
How is the input given? There can be exponentially many O_{ijk...}'s, are these all listed?
Mohammad
CC BY-SA 3.0
2012-07-27T00:58:18.107Z
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.
Masood_mj
<cc.complexity-theory><np-hardness><approximation-algorithms><packing>
bin packing with overlapping objects
Masood_mj
# bin packing with overlapping objects

(Asked by: username_0 on 2012-07-26)

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?

**Tags:** cc.complexity-theory, np-hardness, approximation-algorithms, packing
> **Comments:**
> **username_1**: How is the input given? There can be exponentially many O_{ijk...}'s, are these all listed?  
> **username_0**: 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.  

---

## 3 answers

### Answer by username_2 on 2012-07-27. Score: 6 | Accepted answer

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](http://lass.cs.umass.edu/papers/pdf/SindelarSS11.pdf)


---

### Answer by username_3 on 2012-08-01. Score: 1

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.


---

### Answer by username_1 on 2012-07-27. Score: 1

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.

> **Comments:**
> **username_0**: 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?  

---

