南京大学：《高级算法 Advanced Algorithms》课程教学资源（课件讲稿）09 Rounding Dynamic Programs

Advanced Algorithms Rounding Data 尹一通Nanjing University,2022Fall

尹⼀通 Nanjing University, 2022 Fall Advanced Algorithms Rounding Data

Knapsack Problem Instance:n items i=1,2,...,n; weights w1,,wn∈Z+;valuesv1,,yn∈Zt; knapsack capacity BEZ; Find a subset of items whose total weight is bounded by B and total value is maximized. weight6 capacity B weight values value weight value2 weights values weight3 value3 value4

Knapsack Problem Instance: items ; weights ; values ; knapsack capacity ; Find a subset of items whose total weight is bounded by and total value is maximized. n i = 1,2,…, n w1, …,wn ∈ ℤ+ v1,…, vn ∈ ℤ+ B ∈ ℤ+ B weight1 value1 weight2 value2 weight3 weight value3 4 value4 weight5 value5 weight6 value6 capacity B

Knapsack Problem Instance:n items i=1,2,...,n; weights w1,,wn∈Z+;values v1,,yn∈Zt; knapsack capacity B E; Find an S {1,...,n}that maximizes ∑es subject to∑icsW:≤B. weight6 capacity B weight ·0-1 Knapsack value6 value problem ·one of Karp's21 weight value2 NP-complete problems weights values weight3 OO元eigh value3 value4

Knapsack Problem Instance: items ; weights ; values ; knapsack capacity ; Find an that maximizes subject to . n i = 1,2,…, n w1,…,wn ∈ ℤ+ v1,…, vn ∈ ℤ+ B ∈ ℤ+ S ⊆ {1,…, n} ∑i∈S vi ∑i∈S wi ≤ B weight1 value1 weight2 value2 weight3 weight value3 4 value4 weight5 value5 weight6 value6 capacity B • 0-1 Knapsack problem • one of Karp’s 21 NP-complete problems

Greedy Can Fail Badly Instance:n items i=1,2,...,n; weights w1,,wn∈Z+;valuesv1,,yn∈Z+； knapsack capacity B E+; Find an S)that maximizes s subject to∑icsM≤B. Greedy Fit: Sort items non-decreasingly in v:/w; scan items one-by-one in that order,for each item: include the item in the knapsack if it fits; approximation ratio:arbitrarily bad

Greedy Can Fail Badly Instance: items ; weights ; values ; knapsack capacity ; Find an that maximizes subject to . n i = 1,2,…, n w1,…,wn ∈ ℤ+ v1,…, vn ∈ ℤ+ B ∈ ℤ+ S ⊆ {1,…, n} ∑i∈S vi ∑i∈S wi ≤ B Greedy Fit: Sort items non-decreasingly in ; scan items one-by-one in that order, for each item: include the item in the knapsack if it fits; vi/wi approximation ratio: arbitrarily bad

Dynamic Programming Instance:n items i=1,2,...,n; weights w1,,wn∈Z+;values v1,,yn∈Zt; knapsack capacity B E; 。Define: A(i,v)minimum total weight of S {1,2,...,i} with total value exactly v A(i,v)oo if no such S exists Answer to the knapsack problem: max{v|A(n,v)≤B}

• Define: • Answer to the knapsack problem: max {v ∣ A(n, v) ≤ B} Dynamic Programming Instance: items ; weights ; values ; knapsack capacity ; n i = 1,2,…, n w1,…,wn ∈ ℤ+ v1,…, vn ∈ ℤ+ B ∈ ℤ+ minimum total weight of with total value exactly A(i, v) ≜ S ⊆ {1,2,…, i} v A(i, v) ≜ ∞ if no such S exists

Dynamic Programming Instance:n items i=1,2,...,n; weights w1,,wn∈Z+;values v1,,yn∈Zt; knapsack capacity BEZ; 。Define: mim∑esif3S1…is.tv=y A(i,v)= :了ΣjeSy=v j∈S otherwise Answer to the knapsack problem: max{v|A(n,v)≤B

• Define: • Answer to the knapsack problem: max {v ∣ A(n, v) ≤ B} Dynamic Programming Instance: items ; weights ; values ; knapsack capacity ; n i = 1,2,…, n w1,…,wn ∈ ℤ+ v1,…, vn ∈ ℤ+ B ∈ ℤ+ A(i, v) = min S ⊆ {1,…, i} ∑j∈S vj = v ∑j∈S wj if ∃S ⊆ {1,…, i} s.t. v = ∑ j∈S vj ∞ otherwise

Dynamic Programming Instance:n items i=1,2,...,n; weights w1,,wn∈Z+;values v1,,yn∈Zt; knapsack capacity B EZ; A(i,v)≌minimum total weight of S≤{l,2,.,i} with total value exactly v .Recursion:forl≤i≤n and 1≤v≤V=∑；y A(i,v)=minA(i-1,v),A(i-1,v-v)+wi for i>1 A(1,)= ifv=v1 Dynamic Programming: O.W. Total time costonom Table size:n×V. ·Output::max{vlA(n,)≤B} Time?

• Recursion: for and for • Output: 1 ≤ i ≤ n 1 ≤ v ≤ V = ∑i vi A(i, v) = min {A(i − 1,v), A(i − 1,v − vi ) + wi} i > 1 A(1,v) = { w1 if v = v1 ∞ o.w. max {v ∣ A(n, v) ≤ B} Dynamic Programming Instance: items ; weights ; values ; knapsack capacity ; n i = 1,2,…, n w1,…,wn ∈ ℤ+ v1,…, vn ∈ ℤ+ B ∈ ℤ+ minimum total weight of with total value exactly A(i, v) ≜ S ⊆ {1,2,…, i} v Dynamic Programming: Table size: . Total time cost: . n × V O(nV) Polynomial Time?

Computational Complexity ·decision problem f:{0,1}*→{0,1} 。formal language L{0,1}*L={x∈{0，l}*|fx)=1〉 poly-time Turing machine (algorithm)M: 3c>0 .Vx∈{0，l}*,M()terminates within)steps length of x (in bits) P,NP:classes of formal languages (decision problems) ·L∈P:3poly--time TM M decides L ·M(x)=1fx∈L ·L∈NP:3 polynomial p(·)and poly-time TM M that verifies L ·x∈L→3 certificate y∈{0,1}*of length p(x),M(x,y)=l; ·x庄L→y∈{0，l}*of length p(xl),M(x,y)=0;

• decision problem • formal language • poly-time Turing machine (algorithm) : • , terminates within steps • : classes of formal languages (decision problems) • : poly-time TM decides • iff • : polynomial and poly-time TM that verifies • certificate of length , ; • of length , ; f : {0,1}* → {0,1} L ⊆ {0,1}* L = {x ∈ {0,1}* ∣ f(x) = 1} M ∃c > 0 ∀x ∈ {0,1}* M(x) O(| x | c ) P, NP L ∈ P ∃ M L M(x) = 1 x ∈ L L ∈ NP ∃ p( ⋅ ) M L x ∈ L⟹∃ y ∈ {0,1}* p(| x |) M(x, y) = 1 x ∉ L⟹ ∀y ∈ {0,1}* p(| x |) M(x, y) = 0 Computational Complexity length of x (in bits)

Dynamic Programming Instance:n items i=1,2,...,n; weights w1,,wn∈Z+;values v1,,yn∈Z+; knapsack capacity BEZ; Polynomial-time Algorithm A: c >0,V input x,A(x)terminates within O(x)steps x=length of input x(in binary code) Pseudo-polynomial-time Algorithm A: above definition (except x=length in unary code) ER3O0m V=∑ Total timeǒiomia Time!

• Polynomial-time Algorithm : , input , terminates within steps length of input (in binary code) • Pseudo-polynomial-time Algorithm : above definition (except length in unary code) A ∃c > 0 ∀ x A(x) O(| x | c ) | x | = x A | x | = Dynamic Programming Instance: items ; weights ; values ; knapsack capacity ; n i = 1,2,…, n w1,…,wn ∈ ℤ+ v1,…, vn ∈ ℤ+ B ∈ ℤ+ Dynamic Programming: Table size: . Total time cost: . n × V V = ∑ O(nV) i vi Pseudo￾Polynomial Time!

Scaling Rounding Instance:n items i=1,2,...,n; weights w1,,wn∈Z+;valuesv1,,yn∈Zt; knapsack capacity B EZ; DP with truncated precision: Set k (to be determined); for i=1.2....,n:let v=vk; return the knapsack solution found by DP using new values v(but old weights w;and capacity B); Vi 三 k max max vi 1≤i≤n

Scaling & Rounding 0 vi : ⏟ k vmax = max 1≤i≤n vi DP with truncated precision: Set (to be determined); for : let ; return the knapsack solution found by DP using new values (but old weights and capacity ); k = i = 1,2,…, n v′ i = ⌊vi/k⌋ v′ i wi B Instance: items ; weights ; values ; knapsack capacity ; n i = 1,2,…, n w1,…,wn ∈ ℤ+ v1,…, vn ∈ ℤ+ B ∈ ℤ+