Re: Packing Problem

On May 19, 1:36 pm, David C. Ullrich <dullr...@xxxxxxxxxxx> wrote:
Say we have a bunch of objects of varying sizes
that we want to pack into a bunch of fixed-size
bins - the problem is to find the packing that
minimizes the number of bins. (To clarify
various possible ambiguities, say they're files
in a directory on a computer that we want to
backup onto a bunch of CD's.)

My impression is that no efficient algorithm
for an optimal solution is known(?). My much
weaker impression is that this problem is known
to be in class [whatever], so that an optimal
solution would be equivalent to an optimal solution
to many other problems(?).

But this is not homework - I actually _do_ have
a bunch of files that I want to back up onto a
pile of CDs. Does the obvious algorithm give
a solution that's close to optimal? (I haven't
tried to look up the answer, thinking that
someone who knows would enjoy explaining; also
if I just looked up the answer then it wouldn't
appear here on sci.math).

Also are there any reasonably simple improvements
to the obvious algorithm that give results enough
better to be worthwhile?

What I mean by the obvious algorithm: Sort
the files in order of decreasing size F_1, F_2,...
Number the CDs, C_1, C_2, ... . Put F_1 on C_1.
For each n in turn, put F_n on C_m, where m is
the smallest number such that C_m still has
room for F_n.

David C. Ullrich

I forgot to mention that the problem has the fascinating property that
the well-performing heuristics can nevertheless give strange
behaviour: in the worst case, one can remove items to be packed and
get a solution requiring more bins than before; or one can decrease
the size of the items but end up using more bins. Of course, optimal
solutions cannot behave like that. Coffman, Garey and Johnson give a
useful survey of various versions of bin packing and heuristic
solution properties at www.research.att.com/~dsj/papers/BPchapter.ps .

R.G. Vickson
.

Relevant Pages

  • Re: Packing Problem
    ... minimizes the number of bins. ... backup onto a bunch of CD's.) ... My impression is that no efficient algorithm ... "The best fit decreasing and first fit decreasing strategies are among ...
    (sci.math)
  • Re: Packing Problem
    ... minimizes the number of bins. ... backup onto a bunch of CD's.) ... My impression is that no efficient algorithm ... useful survey of various versions of bin packing and heuristic ...
    (sci.math)
  • Re: Rabid Soul Searching
    ... several bins, you would need an ... "There exist arrangements of items such that applying the packing ... algorithm after removing an item results in one more bin being ...
    (uk.education.staffroom)
  • Re: Rabid Soul Searching
    ... several bins, ... "There exist arrangements of items such that applying the packing ... algorithm after removing an item results in one more bin being ...
    (uk.education.staffroom)
  • Packing Problem
    ... Say we have a bunch of objects of varying sizes ... minimizes the number of bins. ... My impression is that no efficient algorithm ... for an optimal solution is known. ...
    (sci.math)