• 6.5210/18.415: Advanced Algorithms
  • PSets
  • Calendar
  • Materials
  • Information
  • Online Algorithms

    David Karger


    Definition: competitive ratio


    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:

    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

    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)\).


    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?


    Manasse et al. 1988.


    Greedy doesn’t work:

    Fancy algorithmics:

    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.