1
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – Dmitry
    Jan 25 at 7:52
  • $\begingroup$ O(ln d) is quite a lot. Like needing 50 bins for 100 items instead of 10. $\endgroup$
    – gnasher729
    Jan 25 at 13:26
  • $\begingroup$ @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. $\endgroup$
    – D.W. ♦
    Jan 25 at 19:47
  • $\begingroup$ @D.W., it is a constant-factor approximation for constant $d$ (as in the post, with $d=3$). $\endgroup$
    – Dmitry
    Jan 25 at 20:11
  • $\begingroup$ 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. $\endgroup$
    – Sandra
    Jan 25 at 20:15

1 Answer 1

Reset to default
1
$\begingroup$

Here is the solution when the vector is two-dimensional. This process can be extended exactly in the same way to higher dimensions. As mentioned in the comments https://link.springer.com/content/pdf/10.1007/BF02579456.pdf?pdf=button shows the general solution.

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$.

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.