**A new variable-sized bin packing problem***Joan Boyar, Lene M. Favrholdt*

Journal of Scheduling 2010

The problem of BLASTing a genome against a database of DNA
sequences to identify potential relationships with other genomes
can be divided into subproblems quite naturally.
We consider a setting where the problem is distributed to PCs
having idle time.
This results in a new variant of bin packing, where a rectangle is
divided into smaller rectangles that are to be packed in variable-sized
bins which arrive on-line.
A rectangle fits in a bin, if the *sum* of its height and width is
no more than the size of the bin.
The
goal is to
minimize the total size of the bins used for packing
the entire rectangle.

Simple algorithms exist that work well on small instances of the problem and in the special case where all processors (bins) have the same capacity. We propose an algorithm SliceSquares that works well for more realistic instances in a scenario where the processors vary significantly and arrive on-line.

Last modified: Sun Aug 22 12:04:34 CEST 2010 Joan Boyar (joan@imada.sdu.dk)