OPT is the minimum, over all subsets S of the items, of max{w(S), w(S ')}

Prove that OPT ≥ max_j * w_j

Prove that OPT ≥ 1/2 ·∑ w_j for sum of j=1 to n

There are n items with non-negative weights w1, . . . , wn. For each subset S of the items, define S’s weight as w(S) = ∑_{j∈S } wj , the sum of the weights of the items in S.

Splitting the items into sets S and S' = {1, . . . , n} S such that the max{w(S), w(S)} is minimized.

The set is split by
A = ∅, B = ∅
for i = 1 to n

if w(A) ≤ w(B)
A = A ∪ {i}
else B = B ∪ {i}
return (A, B)