Take the 2-minute tour ×

I use a special variant of BinPack problem. I use a naïve algorithm, atm, so I like to know how it might be called to do some initial research. Or does anyone know how to reduce this problem to something known?

The problem: There are items I and bins B in specific quantity and size.

|I| ∈ ℕ, |B| ∈ ℕ
s : (I ∪ B) → ℕ

The sum of all item-sizes is at least the size of the sum of all bins.

∑ _{i∈I} s(i) ≥ ∑ _{b∈B} s(b)

Each bin has to be filled with items or parts of items so that it is filled completely. s(b,i) is the size of that part of i that is in b, or 0 iff not.

∀ b ∈ B, i ∈ I: s(b,i) ∈ ℕ ∪ {0}
∀ i ∈ I: ∑ _{b∈B} s(b,i) ≤ s(i)
∀ b ∈ B: ∑ _{i∈I} s(b,i) ≥ s(b)

The goal is to minimize the number of item-parts needed to fill all bins.

numparts = |{ (b,i) ∈ B×I | s(b,i)>0 }|
find min(numparts)
share|improve this question
add comment

1 Answer

up vote 0 down vote accepted


It is called bin packing with size preserving fragmentation (BP-SPF).

There exists this paper

Approximation Schemes for Packing with Item Fragmentation Omer Yehezkely (November 2006)

share|improve this answer
add comment

Your Answer


