Design and Analysis of Algorithms

788 Design and Analysis of Algorithms

BIN PACKING

INPUT: t ∈ Q

+

and n objects of sizes a

1

, a

2

, a

3

· · · a

n

∈ (0, t].

OUTPUT: Minimum number of size-t bins needed to pack the objects.

Example:

Let the size of the bins be t = 1. Suppose n = 5 and let the sizes of objects be a

1

= 0.7, a

2

= 0.3, a

3

= 0.4,

a

4

= 0.5, and a

5

= 0.4. We can then pack {a

1

, a

2

} in one bin, {a

3

, a

4

}in a second bin , and a

5

by itself, in a

third bin, therefore the number of bins used by this packing is 3. The bin packing problem is well-known

to be NP-Complete. A connection between MMS and bin packing is as follows:

n jobs with processing times p

1

, p

2

, . . . , p

n

can be assigned to m machines with makespan t iff n objects

with sizes p

1

, p

2

, · · ·, p

n

can be packed ...