Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
How is the input given? There can be exponentially many O_{ijk...}'s, are these all listed? –  Mohammad Jul 27 '12 at 0:13
    
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 Jul 27 '12 at 0:58

3 Answers 3

up vote 4 down vote accepted

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

share|improve this answer

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.

share|improve this answer
    
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 Jul 27 '12 at 5:59

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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