* Monday:    amortized analysis:  union/find.
* Wednesday: amortized analysis:  accounting method, potential method.

* Today:     competetive analysis -- similar to amortized analysis.
	     move-to-front for list accesses

-----------

SKI RENTAL

Every time you go skiing, you can either 
  1) _rent_ skis at $20 per visit; or 
  2) _buy_  skis at $150.

But you're fickle, and you never know if you're ever going to go
skiing again every again.  So what should you do the next time you go
skiing?


This is an ONLINE PROBLEM -- you have to decide what to do in response
to the input, but you get the input as you go (without seeing the
future).

Up until now, we've talked about OFFLINE algorithms, where you see all
the data up front.


Given a stream S of requests s_1, s_2, ...
Must make a decision on how to handle s_i WHEN IT ARRIVES. 

---------

COMPETITIVE ANALYSIS

How do we measure the performance of an online algorithm?
Many possible ways, but here's the one we'll use:

     want to minimize regret.

I.e., compare your online algorithm against the best OFFLINE
algorithm.

 
A:        your online algorithm.
C_A(S):   cost of A on input S.
OPT:      optimal offline algorithm.
C_OPT(S): cost of OPT on input S.

A is ALPHA-COMPETITIVE if

  exists k
    for all S
      C_A(S) <= alpha * C_OPT(S)  +  k.

That is, we're always within a factor alpha of the optimal (offline)
algorithm.



-------
A SKI RENTAL ALGORITHM

Should always buy immediately or never.  (offline)

What about online?

Let M be the amount of money I've spent so far.

If M + cost of renting < cost of buying,
  then rent
  else buy.


if (cost of renting)*|S| > cost of buying
  then
     cost_A = (cost of renting)*|S| = cost_OPT.

  otherwise,
     cost_A = (cost of renting until would exceed cost of buying) 
                  + cost of buying
            < 2 * cost of buying = 2 * cost_OPT.


So this algorithm is 2-competitive.



-------

SELF-ORGANIZING LISTS

You're given a linked list of n elements.

S = series of searches for elements.
cost of a search == position in list.
also:  can swap adjacent elements in the list at cost one.

Worst-case:  adversary always searches for last element of list.
	     ==> cost = Omega(|S| n).



An online algorithm:

 MOVE TO FRONT (MTF)
   every time an element is accessed, swap it all the way to the front
   of the list.


  "Amortized Efficiency of List Update and Paging Rules"
  Daniel Sleator and Robert Tarjan
  http://doi.acm.org/10.1145/2786.2793

  -- notes:  accessing ith element costs i.
	     rearranging costs 1 (transposing).
  -- paper:  free to swap before accessed element.
	     (this is probably not worth doing -- maybe mention at the end.)


THEOREM:  MTF is 4-competitive.
pf.  Suppose that ith search is for x_i.

     L_i  := MTF's list before ith access.
     L*_i := OPT's list before ith access.
     c_i  := MTF's cost for ith access.      == 2 * position of x in L_{i}
                                                (one for search, one for swaps)
     c*_i := OPT's cost for ith access.      == position of x in L*_{i} + t_i
                                                   t_i := # of swaps by OPT.

 
Define potential function
     Phi(L_i) := 2 * # of inversions between L_i and L*_i.

note Phi(L_0) = 0.  (start with same lists)
     Phi(L_i) >= 0.


Now define

     A := elements preceeding x_i in both L_i and L*_i.
     B := elements preceeding x_i in L_i but succeeding x_i in L*_i.
     C := elements succeeding x_i in L_i but preceeding x_i in L*_i.
     D := elements succeeding x_i in both L_i and L*_i.
     

L_i:    A/B  x   C/D.
L*_i:   A/C  x   B/D.

	
    so cost_mtf = 2(|A| + |B| + 1)
       cost_opt =  (|A| + |C| + 1) + t_i (== #swaps performed by OPT).


Consider the amortized cost of MTF:

amortized-cost = cost_mtf         + Phi(L_i) - Phi(L_{i-1}).
	       = 2(|A| + |B| + 1) + 2*(increase in the # of inversions)

	       
so how many inversions are created and destroyed?
   when we mtf, bx was an inversion before but now we have xb.    -|B|
	        ax was not an inversion before now we have xa.    +|A|.

   how about changes that OPT makes?
   well, can create at most t_i inversions!                    <= +t_i

amortized-cost <= 2(|A| + |B| + 1) + 2(|A| - |B| + t_i)
	       <= 4|A|         + 2               + 2t_i 
               <= 4(|A| + 1 + t_i)
	       <= 4((|A| + |C| + 1) + t_i)
	        = 4*cost_opt.




-------
APPROXIMATION ALGORITHMS

As an aside:

   a related notion -- an ALPHA-APPROXIMATION ALGORITHM.

   an algorithm A (offline) is an ALPHA-approximation for a problem if
   cost(A) <= ALPHA * cost(OPT).

   
   for example (though this is nontrivial to prove):
     -- "sort the books, then use "first pack"
          (that is, put the book in the first box that it'll fit into)"
        is something like an 11/9-approximation to the book-packing problem.