1 of 23

Lower Bound Against Oblivious Adversaries

2 of 23

Reminder: Paging

  • Input: A bounded cache size k. A sequence of page requests.�
  • Output: When a sequence page p is not in the cache (‘page fault’) - decide which cache page is discarded to make room for p.�
  • Goal: Minimize the number of page faults throughout the sequence.�

3 of 23

Reminder: Paging

  •  

4 of 23

Yao’s Minimax Principle

  •  

5 of 23

Yao’s Minimax Principle

  •  

6 of 23

Yao’s Minimax Principle

  •  

7 of 23

Yao’s Minimax Principle

  •  

8 of 23

Yao’s Minimax Principle

  •  

1

A randomized algorithm is a distribution over deterministic algorithms

9 of 23

Lower Bound For Paging

  •  

10 of 23

Lower Bound For Paging

  • 1,2,3,4,5,6,3,2,3,5,1,6,5,4,6,5,4,3,2,3,2,3,2,1…�
  • How many faults does OPT have in every phase?�
  • Exactly one fault.�
  • Let A be a deterministic algorithm. How many fault, in expectation, A has in a phase?

11 of 23

Lower Bound For Paging

  •  

12 of 23

Lower Bound For Paging

  •  

13 of 23

Lower Bound For Paging

  •  

14 of 23

Lower Bound For Paging

  •  

15 of 23

Lower Bound For Paging

  •  

16 of 23

Online Knapsack

  •  

17 of 23

Online Knapsack

  •  

18 of 23

Online Knapsack

  •  

19 of 23

Online Knapsack – Oblivious Adversary

  •  

20 of 23

Online Knapsack – Oblivious Adversary

  •  

21 of 23

Online Knapsack – Oblivious Adversary

  •  

22 of 23

Online Knapsack – Oblivious Adversary

  •  

23 of 23

Online Knapsack – Oblivious Adversary

  •