Primal-Dual Algorithm ·x=0,yj=0 for each newj=1,2,...,k ifx <1 x←X+ B where c=(1+2)1 1 十 ☑=1-x y5=1 Intuitively,at j-th round,we rent with probability ZiPrimal-Dual Algorithm • 𝑥 = 0, 𝑦𝑗 = 0 for each new 𝑗 = 1,2,… , 𝑘 if 𝑥 < 1 𝑥 ← 𝑥 + 𝑥 𝐵 + 1 𝑐𝐵 , where 𝑐 = 1 + 1 𝐵 𝐵 − 1 𝑧𝑗 = 1 − 𝑥 𝑦𝑗 = 1 • Intuitively, at 𝑗-th round, we rent with probability 𝑧𝑗