# Bin packing with more than one parameter

Usually, in bin-packing, we have objects of sizes $$a_1,...a_n$$, and each bin has size 1, We need to minimize the number of bins, and for this, there are best fit/first-fit approximation algorithms.

What will happen if there are more parameters than just size, say 3 parameters? Each object $$i$$ has say parameters $$(a_i,b_i,c_i)$$ and there are bins with all the three parameters equal to 1. How can we extend the best-fit/first-fit approximation algorithms, so that in each bin, we have $$\sum a_i \leq 1, \sum b_i \leq 1,\sum c_i \leq 1$$ and we still have a constant approx factor?

• The keywords are "multidimensional bin packing" and "vector bin packing". Multidimensional Bin Packing and Other Related Problems: A Survey, Section 4.1 says: "for fixed $d$ (In your example, $d=3$), vector bin packing can be approximated to within $O(\ln d)$ in polynomial time". You can check the survey for more detail. Jan 25 at 7:52
• O(ln d) is quite a lot. Like needing 50 bins for 100 items instead of 10. Jan 25 at 13:26
• @Dmitry, perhaps you would like to write that as an answer, so we can upvote it? I realize it is not a constant-factor approx.
– D.W.
Jan 25 at 19:47
• @D.W., it is a constant-factor approximation for constant $d$ (as in the post, with $d=3$). Jan 25 at 20:11
• I read the survey mentioned by Dmitry and it says that you cannot get a constant approximation factor for d-dimensional vector bin packing when $d>2$, where $d$ is an input parameter, not a constant. For the case $d=2$, some clever papers are there which produce very small approximation factors. link.springer.com/content/pdf/10.1007/BF02579456.pdf?pdf=button pg 354 (pg 6) gives an "easy-to-understand" approximation. Jan 25 at 20:15

Z is the set of vectors given to us. Let $$L_i$$ denote the set of indices of the vectors in $$Z$$ for each of which the largest component is the $$ith$$ one, breaking ties arbitrarily. Now consider all the vectors whose index has been put inside $$L_i$$ and then let's call $$Z_i$$ the list of the values of the $$ith$$ component of the vectors. An optimal packing of $$Z_i$$ will be an optimal packing for the vectors inside $$L_i$$. We already know that for 1-dimensional packing we can do a greedy best fit or first fit algorithm with an approximation factor of 2. We apply that greedy algorithm to this one-dimensional packing we got. Say we can optimally pack the $$Z_i$$ in $$Z_i^*$$ bins. Then for the two-dimensional case, we will not need any more than $$2 \cdot (Z_1^* + Z_2^*)$$ bins for packing all the vectors in $$Z$$.
Again observe that all those vectors that have indexed in $$L_i$$ cannot be packed in less than $$Z_i^*$$ bins. So if $$Z^*$$ is the optimal number of bins for all the vectors(i.e. OPT in this case), then $$Z^* \geq max\{Z_1^*, Z_2^*\} \geq 1/2 \cdot (Z_1^* + Z_2^*)$$. Combining both the inequalities, we see that our algorithm will obtain an approximation factor of 4, i.e. $$2 \cdot (Z_1^* + Z_2^*) \leq 4 \cdot max\{Z_1^*, Z_2^*\} \leq 4 \cdot OPT$$.