Online Algorithms
6.854 Notes #25

David Karger

1 Online algorithms


Definition: competitive ratio

1.1 Finance

Known or unknown duration. But assume know which offer is last.

Need fluctuation ratio \(\phi\) between largest \(M\) and smallest \(m\) price.

Selling peanuts:

Selling (one) car: Best deterministic algorithm: agree to first price exceeding \(\sqrt{Mm}\)

Can achieve \(\log \phi\) randomized

Graham’s Rule

Define \(P||\max C_j\) to minimize load.

NP-complete to solve exactly!

Always assign to least loaded machine:

More recent algs do somewhat better:

1.2 Paging problem

Easy argument: \(k+1\) competitive

With work, we can improve to \(k\) (worth it for tightness):

Generalize: LRU is \(k/(k-h+1)\) competitive against \(h\)-page adversary


Lower bound: no online algorithm beats \(k\)-competitive.


Optimal offline algorithm: Longest Forward Distance

1.3 Move to front

Studying heuristics for reorganizing a list after you access it

Potential function: number of inversions.


Lower bound:

Note: our competitive bound assumes opt is paying 1 for transposes

2011 End lecture 20

Randomized Online Algorithms

An online algorithm is a two-player zero sum game between algorithm and adversary. Well known that optimal strategies require randomization.

A randomized online algorithm is a probability distribution over deterministic online algorithms.

Algorithm is \(k\)-competitive if for any \(\sigma\), \(E[C_A(\sigma)] \le k\cdot OPT+O(1)\).


1.3.1 Randomized Paging

Idea: evict random page?

Marking algorithm:

Fiat proved: Marking is \(O(\log k)\) competitive for \(k\) pages.



Online cost:

Offline cost:

Summary: If online pays \(x\log k\), offline pays \(x/2\). So, \((\log k)\)-competitive.

Lower Bounds via Yao’s Minimax Principle

Online algorithms is a two player game:


For paging:

This analysis applies to an oblivious adversary. What about other models?

1.4 \(k\)-server

Manasse et al. 1988.


Greedy doesn’t work:

Fancy algorithmics:

1.4.1 On a Line

A truly “On Line” algorithm.

greedy algorithm bad if requests alternate \(a\) near \(b\) but server on distant \(c\).


Problem: which of two nearest to move?

double coverage algorithm (DC):



Can we do better? No, because paging is special case.