OPT is the minimum, over all subsets S of the items, of max{w(S), w(S ')} Prove that
Fantastic news! We've Found the answer you've been seeking!
Question:
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)
Related Book For
South Western Federal Taxation 2014 Comprehensive Volume
ISBN: 9781285180922
37th edition
Authors: William H. Hoffman, David M. Maloney, William A. Raabe, James C. Young
Posted Date: