Re: Packing Problem
- From: Ray Vickson <RGVickson@xxxxxxx>
- Date: Mon, 19 May 2008 13:52:34 -0700 (PDT)
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
It seems that you have rediscovered the first fit decreasing
heuristic.
The problem is NP-hard, but quite good heuristics are known for it.
See the Wiki article http://en.wikipedia.org/wiki/Bin_packing_problem
(which, unlike some, is pretty accurate). In particular, it says:
"The best fit decreasing and first fit decreasing strategies are among
the simplest heuristic algorithms for solving the bin packing problem.
They have been shown to use no more than 11/9 OPT + 1 bins (where OPT
is the number of bins given by the optimal solution)[1]. The simpler
of these, the First Fit Decreasing strategy, operates by first sorting
the items to be inserted in decreasing order by volume, and then
inserting each item into the first bin in the list with sufficient
remaining space. The sorting step is relatively expensive, but without
it we only achieve the looser bound of 17/10 OPT + 2. A more efficient
version of FFD uses no more than 71/60 OPT + 1 bins ([2][3]).
Recently, it was proved that the bound 11/9 OPT + 6/9 for FFD is tight
[4]."
R.G. Vickson
.
- References:
- Packing Problem
- From: David C . Ullrich
- Packing Problem
- Prev by Date: Re: Can you trim a FFT?
- Next by Date: Re: volume of a cone
- Previous by thread: Packing Problem
- Next by thread: Re: Packing Problem
- Index(es):
Relevant Pages
|
Loading
