Deterministic algorithm There is a simple deterministic algorithm s.t. our cost is at most 2.minfk,B. We then say that the algorithm has a competitive ratio of 2. Algorithm: On each day j<B,rent. On day B,buy. If k B,then our cost is k,which is optimal. ■Ifk≥B,then our cost is B-1+B=2B-1<2B=2·mink,B} 6
Deterministic algorithm ◼ There is a simple deterministic algorithm s.t. our cost is at most 2 ⋅ min{𝑘, 𝐵}. ❑ We then say that the algorithm has a competitive ratio of 2. ◼ Algorithm: On each day 𝑗 < 𝐵, rent. On day 𝐵, buy. ◼ If 𝑘 < 𝐵, then our cost is 𝑘, which is optimal. ◼ If 𝑘 ≥ 𝐵, then our cost is 𝐵 − 1 + 𝐵 = 2𝐵 − 1 < 2𝐵 = 2 ⋅ min 𝑘, 𝐵 6
Randomized algorithm It turns out to exist a randomized algorithm witha competitive ratio of。号≈1.58 The algorithm uses integer programming and linear programming
Randomized algorithm ◼ It turns out to exist a randomized algorithm with a competitive ratio of 𝑒 𝑒−1 ≈ 1.58 ◼ The algorithm uses integer programming and linear programming. 7
Integer programming There is an integer programming to solve the offline version of the ski-rental problem. ■Ve introduce some variables x,zi,z2,.,zk∈ {0,1}. x:indicate whether we eventually buy it. zi:indicate whether we rent on day i. IP: min B·x+=1Z1 s.t.x+z1≥1， j∈[k] x,Z∈{0,1 j∈[k] 8
Integer programming ◼ There is an integer programming to solve the offline version of the ski-rental problem. ◼ We introduce some variables 𝑥, 𝑧1 , 𝑧2 ,… , 𝑧𝑘 ∈ 0,1 . ❑ 𝑥: indicate whether we eventually buy it. ❑ 𝑧𝑖 : indicate whether we rent on day 𝑖. ◼ IP: min 𝐵 ⋅ 𝑥 + σ𝑗=1 𝑘 𝑧𝑗 𝑠.𝑡. 𝑥 + 𝑧𝑗 ≥ 1, ∀𝑗 ∈ 𝑘 𝑥, 𝑧𝑗 ∈ 0,1 ∀𝑗 ∈ 𝑘 8
Solution It's not hard to see that the optimal solution to the IP is x=0,zi=1,if k<B x=1,z1=0,ifk≥B 口 same as the previous optimal solution for the offline problem. ■ So the IP does solve the offline problem
Solution ◼ It’s not hard to see that the optimal solution to the IP is ൝ 𝑥 = 0, 𝑧𝑗 = 1, if 𝑘 < 𝐵 𝑥 = 1, 𝑧𝑗 = 0, if 𝑘 ≥ 𝐵 ❑ same as the previous optimal solution for the offline problem. ◼ So the IP does solve the offline problem. 9
Relaxation Relax it to LP. IP: minB·x+=1z S.t.x+zj≥1， j∈[k] x,zj∈{0,1 j∈[k] LP: min B·x+=1Z s.t.x+zj≥1， viEk x≥0，z1≥0， j∈[k] 10
Relaxation ◼ Relax it to LP. ◼ IP: min 𝐵 ⋅ 𝑥 + σ 𝑗 = 1 𝑘 𝑧𝑗 𝑠.𝑡. 𝑥 + 𝑧𝑗 ≥ 1 , ∀𝑗 ∈ 𝑘 𝑥 , 𝑧𝑗 ∈ 0 , 1 ∀𝑗 ∈ 𝑘 ◼ L P: min 𝐵 ⋅ 𝑥 + σ 𝑗 = 1 𝑘 𝑧𝑗 𝑠.𝑡. 𝑥 + 𝑧𝑗 ≥ 1 , ∀𝑗 ∈ 𝑘 𝑥 ≥ 0 , 𝑧𝑗 ≥ 0 , ∀𝑗 ∈ 𝑘 10