Randomized paging, packing/covering linear programs, weak duality, approximate complementary slackness, primal/dual online algorithms (2-competitive deterministic ski rental).

2HK Competativeness.

Citation

This lecture goes over the details of the Mark algorithm.

You can get a competitive ratio of e over e over e-1

Online set cover.

Advanced Algorithms (COMPSCI 224), Lecture 9 | Online Primal Dual

Online Primal Dual is built around linear programming.

Advanced Algorithms (COMPSCI 224), Lecture 9

Fiat et al Mark J Algebra 91'

Initially, all pages are marked.

When bringing page p into cache. Evict a uniformly random, unmarked page. Then mark p.

Developed by Buchbinder and Nauer in 2005.

See 2hk competitiveness for randomized paging. The Mark algorithm. We'll see online primal-dual as well.