8
$\begingroup$

Bin packing problem is a problem, where one has to find the minimum number of bins of size $v$ required to store $n$ objects of sizes $s_1, \ldots, s_n$. Object sizes are never greater than $v$.

For example, if $v = 10$ and the objects sizes are $2, 5, 4, 7, 1, 3, 8$, we can store objects with 3 bins: $[8, 2], [7, 3], [5, 4, 1]$, but not with 2 bins or less, as this would leave some items unpacked. Therefore 3 is the minimum number of bins required, and $[8, 2], [7, 3], [5, 4, 1]$ is an optimal solution.

The best-fit-decreasing heuristic is a packing strategy, which aims to produce a packing close to optimal. It first sorts all the items in descending order. Then it iterates over all items, and for each item attempts to find an existing bin, which can both fit the item and whose spare capacity is closest to the size of the item. If such bin exists, it puts the object in the bin. If it doesn't, it creates a new bin and puts it there.

A non-trivial bin-packing instance is an instance of the problem, which can't be optimally solved by the best-fit-decreasing heuristic.

For example, the instance $v = 7$, $n=6$ where sizes are $3, 2, 3, 2, 2, 2$ is non-trivial, because the best-fit decreasing heuristic will:

  1. Sort the items to give $3, 3, 2, 2, 2, 2$
  2. Put the first two items in the first bin, producing a bin $[3, 3]$
  3. Put the next three items in the second bin, producing a bin $[2, 2, 2]$
  4. Put the last item in the third bin, producing a packing $[3, 3], [2, 2, 2], [2]$

This is a valid packing, but non-optimal, as it requires 3 bins, and there exists a valid packing with two bins: $[3, 2, 2], [3, 2, 2]$.

Is there a non-trivial bin-packing instance with $n=5$?

$\endgroup$
2
+50
$\begingroup$

No, there is no such instance for any $n\le 5$. Indeed, assume to the contrary. Pick the smallest $n$ for which $O<A$, where $O$ is the number of bins in an optimal packing and $A$ be the number of bins in a packing found by best-fit-decreasing heuristic. Enumerate the objects in such an order that $s_1\ge s_2\ge\dots\ge s_n$. Now we use the following simple observations.

If $O=1$ then $A=1$.

Assume that in an optimal packing there exists a bin containing only one object. But, since $s_1\le v$, without loss of generality we may assume that the bin contains Object 1 and the other objects placed into the first bin by best-fit-decreasing heuristic. Removing these objects from the object list, we reduce the problem to a smaller number of objects, which contradicts the minimality of $n$.

The above observations imply that $O=2$, because otherwise since $n<6$ in each optimal packing there exists a bin containing only one object. Now fix and optimal packing and consider a bin containing Object $1$. If the bin contains at lest two other objects then it can be easily checked that $A=2$. If the bin contains at most one other object $i$ then the other bin contains all remaining objects. Then in the packing created by best-fit-decreasing heuristic the first bin contains at least Object $1$ and Object $j$ with $j\le i$, so the second bin contains all other objects, because it is able to contain them, so $A=2$.

$\endgroup$
22
  • $\begingroup$ Apologies, but I'm having difficulties understanding your proof: "Assume that in an optimal packing there exists a bin containing only one object. But, since $s_1≤v$, without loss of generality we may assume that the bin contains Object 1 and the other objects placed into the first bin by best-fit-decreasing heuristic." Is the following a valid counterexample to what you're proposing: v=7, packing = [3, 3], [2]. Clearly this is an optimal packing. There is a bin, which contains only one object. But that bin does not contain object 1. $\endgroup$ Nov 25 '17 at 15:34
  • $\begingroup$ It is a minor nit-pick, but in the first sentence you clearly do not assume the converse, you assume the opposite. $\endgroup$ Nov 25 '17 at 15:35
  • $\begingroup$ Also $s_1 ≥ s_2 ≥ ⋯ ≥ s_5$ is should be $s_1 ≥ s_2 ≥ ⋯ ≥ s_n$, where n is the index with the smallest counterexample. $\endgroup$ Nov 25 '17 at 16:01
  • 1
    $\begingroup$ Of course, you're right. The minimal counterexample part of the proof is perfect. It's just written really tersely and I got confused. $\endgroup$ Nov 30 '17 at 19:53
  • 1
    $\begingroup$ That's perfect. It's a neat proof. $\endgroup$ Dec 1 '17 at 9:59
0
$\begingroup$

Define a set of objects $x_1,x_2, ... ,x_k$ to dominate a set of objects $y_1,y_2, ... ,y_l$ if $k\ge l$ and $x_i\ge y_i$ for $1\ge i\ge l.$ If set $X$ dominates set $Y$, then the existence of a solution with $n$ bins for $X$ implies a solution with $n$ bins for $Y$.

Now suppose there to be a solution with fewer bins {$A_i$} than the first-fit solution and let $B_1$ be the first bin in the first-fit solution. The contents of $B_1$ cannot be dominated by the contents of any $A_i$ by definition of the first-fit algorithm. Furthermore, the contents of $B_1$ cannot dominate the contents of any $A_i$, for if it did then the objects remaining for the other $B_i$ would be dominated by those remaining for the other $A_i$ and we would have another non-trivial bin packing with fewer objects and we can restrict this analysis to that smaller example!

Let $A_1$ be a bin containing the largest object $s$. Now $B_1$ must, of course, contains $s$ and the non-dominating result means that $B_1$ must contain at least two objects. The non-dominating result then means that each $A_i$ must contain at least three objects and this is why $n$ must be at least 6.

$\endgroup$
9
  • $\begingroup$ "The contents of B1 cannot be dominated by the contents of any Ai by definition of the first-fit algorithm." Of course it can. If A1 and B1 contain the same elements, then B1 is dominated by A1. Why should A1 and B1 contain different objects? $\endgroup$
    – miracle173
    Nov 30 '17 at 9:18
  • $\begingroup$ "the contents of B1 cannot dominate the contents of any Ai" if A1 adn B1 contain the same objects then B1 dominates A1 $\endgroup$
    – miracle173
    Nov 30 '17 at 9:19
  • $\begingroup$ your definition of dmination is not precise. I think you shoud add that x1,x2,... and y1,y2,... are non decreasing sequences. Otherwise a set counld be dominated and not dominated at the same time. $\endgroup$
    – miracle173
    Nov 30 '17 at 9:22
  • $\begingroup$ If the bins A1 and B1 contained the same elements then there would be the reduction to fewer objects described in my solution. Furthermore there is no need for the suggested ordering of the objects. $\endgroup$
    – S. Dolan
    Nov 30 '17 at 17:04
  • $\begingroup$ But you wrote in your answer "cannot be dominated [...] by definition of the first-fit algorithm" which is worng, so it would be fine if you repair your answer. 1,2,3 is dominated by 2,3,4 but 3,2,1 is not dominated by 2,3,4. But 1,2,3 and 3,2,1 are the same set. So the set is dominated and not dominated by 2,3,4. That does not look good. $\endgroup$
    – miracle173
    Nov 30 '17 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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