Bin Packing

Farnandez DelaVega Approach:

1. LP is based on configurations (m-tuple where m is the types of items).

2. No. of configurations exponential to m. To reduce configurations/constraints ignore items with size e/2.

3. Linear grouping. OPT(I')+k are sufficient to pack items after rounding and discarding on (n/k) groups. First group discarded rest are rounded to the highest size in the group.

m= n/k <>

Rounded items are packed in OPT+2/(e^2).

Discarded items need e.OPT.(e.OPT is given to pack k extra items k.SIZE(I).)

Small discarded items are in 1 bin.

(1+e)OPT+ 2/(e^2) +1 bins.

================================================================

Karp-Karmarkar Approach:

1. a_n>= 1/SIZE(I). -- Smaller pieces are packed later.

2. Geometric Grouping:

pack until total size exceeds 2. So, 2 <= size of gp <=3

G_i is i'th group with n_i elements.

Discard G_1, G_r and n_i - n_(i-1) in G_i.

3. Number of distinct pieces is <= SIZE(I)/2.

Discarded pieces total size = O(log (SIZE(I)))