Packing Problems

Partition Problem

The problem is NP-complete (both determining if there are equally sized heaps and finding the two heaps with the smallest difference).

Can be regarded as a special case of Job Scheduling.

Go through the numbers in S, always assign the current number to the heapS1 or S2 that is currently smaller.

Greedy Algorithm 1 provides a 2-approximation, i.e., sum ofs∈S1 s is at most twice as large as it would be in the optimal partition.

Partition prob greedy algo 2

Sort the numbers in S in descending order.

Go through the numbers in S, always assign the current number to the heap S1 or S2 that is currently smaller.

Greedy Algorithm 2 provides a 6/5-approximation.

Subset Sum

O(nZ) pseudo-polynomial

Knapsack Problem

FORMAL DEFINITION

Given n items gi, each with price pi and weight wi, as well as weight limit W.

Find subset M of items with summation g∈M w(g) ≤ W and summationg∈M p(g) maximal.

Subset Sum is a special case with W = Z, w(s) = s and p(s) = s.

Greedy Knapsack 2

Bin Packing

In Bin Packing, we want to use as few containers as possible to pack all items with a certain volume.

Bin Packing can also be considered in multidimensional space, but we limit ourselves to 1D here.

DEFINITION: Given are containers (bins) with volume V , and n items with volumes v1, . . . , vn. How many bins are minimally necessary to store all items in bins?

First Fit ALGO

Consider items in any order. For each item, go through the existing bins. Place it in the first bin with enough space. If no such bin exists, create a new bin and insert the item there.

First Fit provides a 2-approximation.