Online algorithms and competitive Analysis

part of [[111.00_anchor]]

Definition

#def

“Standard” offline algorithm ::

• When algorithm starts it has complete knowledge about the entire input
• Then the algorithm computes its result and returns one output

In many scenarios this is an unrealistic scenario ::

1. ==Scheduling== want to schedule a number of jobs to a number of machiens, continuously. We have jobs arriving one by one and have they have to be scheduled immediately, without knowing aobut future jobs.
2. Paging in an operating system: decide which “page” to keep in the RAM and which ones to move to the the disk. We want to keep those pages in the RAM that are going to be used the most in future – at least we would like those to be taken – but we dont know the future requests yet!
3. Data structures:: a tree or heap is goig to be maintained throughout the running time of an algorithm. We do not konw in advance which elements we are goign to insert or delete.

Setup of an online algorithm

• Algorithm A gets a request sequence ${\sigma }_1,{\sigma }_2,\dots ,{\sigma }_m$ of inputs.
• At the time of request ${\sigma }_i$ it knows all the past requests ${\sigma }_t$for $t\le i$ but no the future requests ${\sigma }_{j}j>i$
• When the algorithm serves request ${\sigma }_i$ it incurres costs $c_i$. These costs can be running time, but in many contexts they are also something else. For example, in scheduling the costs could be the number of machiens that are idle at a given point in time, or the delay by which a request is served/
• THe cost $A(\sigma )$ of the entire request seqeuence is the sum of the individial requests.

And online algorithm is always able to process the previous events and data, yet never the future !

Competitiv analysis ::

We want to compare the online algorithm with an optimal offline algorithm:: The offline algorithm knows the entire sequence ${\sigma }_1,\dots ,{\sigma }_m$ from the very beginning It then serves all the requests in the same order as the online algorithm, but it is allowed to make use of the knowledge of the whole sequence - in particular of future requests.

An example could be paging THe algorithm konws which are the pages that are going to be requestesd in the future. So it can easily decide which ones should be kept in the worknig memory.

Evaluating online algorithms ::

Definitino of competitiveness ::

• Denote by $OPT(\sigma )$ the cost incurred by the best possible offline algorithm, that is the minimal cost incurred by all possible offline algorithms on the sequence $\sigma$
• Denote by $A(\sigma )$ the costs of online algorithm A on input sequence $\sigma$
• An algorithm is called c-competitive if there exists a constant a such that for all requests $\sigma$ $A(\sigma )\le c\ast OPT(\sigma )+a$ Observer: this is a worst case statement we do not argue about any kind of average case- which may invovle how likely a sequence $\sigma$ is gonna be

We define the online algorithm once for all sequences and should also be able to apply it for every occurring sequence at a later time

Ski Rental problem ::

Scenario ::

We go skiing for the first time and depending on whether you like it or not you might go skiing more often in the future Renting the equipment for a day costs 50€, buying the equipment costs 500€. At each day you can decide :: rent or buy

We could potentially solve the problem with the following system ::

• We encode the events “to ski” or “not to ski” by a sequence $\sigma :=({\sigma }_i{)}_{i\in \mathbb{N}}$ with ${\sigma }_i=1$ or ${\sigma }_i=0$ one ${\sigma }_i$ per day. At each day we decide whether to buy them or not.
• WE encode our rent-or-buy stategy by one number $t\in \mathbb{N}$: the strategy $s_t$ consists of renting the equipment on days $1,\dots ,t-1$ and buying skis on day t.

$S_i$ defines the first strategy :: buying skiis on first day

We have several possible outcomes now:

1. We never go skiing again after the first day : $\sigma =1,0,0,0\dots$ Then $A(\sigma )=500_{initialcost}$ OPT$(\sigma )=50$ hence the competitive ratio $A\frac{\sigma }{OPT(\sigma )}=10$
2. Assume we only go skiing once more after the first day : $\sigma =1,1,0,0\dots$. Then we can conclude :: $A(\sigma )=500OPT(\sigma =100)$ and our ratio is 5
3. We can condlude that the ratio is increasing whenever we go less skiing, and decreases whenever we go driving more and more.

$S_2$ defines the second strategy :: we buy on day 2 ::

It is easy to see that the worst-case-$\sigma$ is that we stop skiing after that given day. We have spent 50 euros on the first day and 500 on the second day - 550 together then - bu the optimal solution would have been ro rent both times - 100 together. Hence the competitive ratio is 5.5.

Next, consider strategy $S_t$ buy on day t for $t\le 10$. It is easy to see that the worst-case-$\sigma$ is to stop skiiing after this day, and that the optimal strategy would be to rent t times. THis leads to the competitive ratio of : $\frac{50(t-i)+500}{50t}=\frac{9+t}{t}$ THe smallest value occurs for t=10 achieving ratio of 1.9

we ought to consider three types of sequences :

1. sequences where you ski less than t days
2. sequences where you ski exactly t days
3. sequences where you ski more than t days

Finally we consider strategy $s_t$: buy on day t for t >10 Here it is easy to see that the worst-case-$\sigma$ is tht we never go skiing again but the optimal strategy would be to buy the equipment on day 1. This would lead to a competitive ratio of: $\frac{50(t-1)+500}{500}=\frac{9+t}{10}\ge 10$

Conclusion ::

==We achieve the best ratio== when we buy on day 10, which gives a competitive ratio fo c= 1.9 >> we cant get lower than this

Note again the intuition :: We look at the worst case mostly. In the worst of all worlds, if you have no control whatsoever on whether you will go skiing ever again, with strategy $s_{10}$ you cannot loose more than a factor 1.9 of money. compared to the optimal strategy.

More generally ::

• Online algorithms are usually used for buy-vs-rent problems :: Keep renting until what we have spent equals the cost of buying. After that buy.
• This algorithm is 2-competitive - with a = 0 - by the same argument as above, for any sequence $\sigma$ we occur at most twice as much costs as the optimal algorithm ==we are only observing the worst case analysis==

List update, caching and paging problem ::

• we would like to maintain a list of items
• Requests are to access, insert or delete an item from the list.
• Exchange operation: requested item may be moved to somewhere else, or two items may be exchanged
• Question: what is the best strategy to maintain the list such that all these operations are “as cheap as possible” in the sense of competitiveness.

if items are accessed often, we should retrieve them easier than the others

What might be a good strategy to maintain the list ?

_There are some approaches available :: _

1. ==Move-to-front== always move the requested item to the lists front
2. ==Transpose== Exchange the requested item with the item in front of it - and thus moving it one position further to the front
3. ==Frequency count== for each itme in the list maintain a frequency count. Maintain the list in such a way that the frequency count is decreasing.

which one is the best ?

==Move-to-front== is the best solution, with 2-competitive

Transpose and frequency-count are not c-competitive for any constant c.

The marriage problem ::

Assume we’ve joined a dating site. Just from looking at profiles of potential partners, you identify n persons that you would like to date. Ideally, yo would like to “try” them all before picking one –> the best probably

How many ppl should we observer before deciding ?

This problem is also called the ==secretary problem==

informal definition ::

We are going to analyze the following strategy $s_t$:

1. order the people in some random order
2. Phase1 : Go out with T people and ditch all of them – we call it ==calibration phase== and it is used to find an average >> late rwe search for all that are better than the first phase
3. Phase 2 : Keep on going out with more people. As soon as you find someone who is better than all the candidates of phase 1 ::Take them!

in this version we never choose the people of the calibration phase again >> even if we have someone who’s the best in there.

formal definition ::

Assume the people are ordered in some random number. We denote $\pi$ the permuttation that re-orders people according to how you like them: $\pi (i)<\pi (j)⟺$ i is better than j Goal is to find the candidate j with $\pi (j)=1$ Our dating strategey is denoted with:: $s_t:$ select the smallest j >t for which $\pi (j)<mi{n}_{i=1\dots ,t}\pi (i)$

We would like to compute the probability that $\pi (j)=1$, which is the probability for the best candidate.

The required calculations::

We define P as the optimal candidate: $P=\sum _{j=t+1}^{n}P(\text{j is the bet one AND we pick j})$ $=\sum _{j=t+1}^{n}P(\pi (j)-1)\ast P(\text{we pick J}|\pi (j)=1=:(\ast ))$

Evaluating $P(\pi (j)=1)$ ::

Are permutations are equally likely to occure, because $P(\pi (j)=1)=\frac{1}{n}$

Evaluating $P(\text{we pick j}|\pi (j)=1)$

We consider the condition that for the given j we have $\pi (j)=1$ The our strategy chooses j if: j is the best candidate among $t+1,\dots ,j-1$ is worse than any of the candidates in 1 to t- which is the calibration set

$⟺$ the best among 1,…,j-1 is contained in 1,…,t $⟺min\{\pi (1),\dots ,\pi (j-1)\}\in \{\pi (1\dots ,\pi (t)\}$ The minimum of above set is equally likely to occur at any of the j-1 positions. In particular, the likelihood that it occurs within the first t elements is $\frac{t}{t-1}$

Result ::

We obtain the total equation of $\sum _{j=t+1}^n\frac{1}{n}\ast \frac{t}{j-1}$ Further calculations - exploit properties of partial sums of harmonic series lead to ::

Result::

Our choosen dating strategy $s_t$, defines the overall likelihood to obtain the best candidate with :$\frac{t}{n}ln\frac{n}{t}$ Easy to see that this term is maximal for t = $\frac{n}{e}$, which give a probability of $\frac{1}{e}$

This solution aint the best and there are several extensions available to improve the algorithm ::

• reduce the search for the top10 best people
• we require to know n prior to calculate everything