A function u : [0, 1] → [0, 1] is dual-feasible if for any sets of numbers w1,w2, . . . , wk, we have

k i1 wi ≤ 1 ⇒

k i1 u(wi ) ≤ 1.

(a) Given an instance of the Bin-Packing Problem with item sizesw1,w2, . . . , wn and a dual-feasible function u, prove that

n i1 u(wi ) ≤ b

∗.

(b) Assume n is even. Let half of the items be of size 2 3 and the other half of size 1 2 . Find a dual-feasible function u that satisfies:
n i1 u(wi )  b ∗
.