# What do you mean by Online algorithm? Explain ski rental problem with its analysis.

**Online Algorithms**

An online problem is one where not all the input is
known at the beginning. Rather, the input is presented in stages, and the
algorithm needs to process this input as it is received.

·
As the algorithm
does not know the rest of the input, it may not be able to make optimum
decisions.

·
How can we
analyze online algorithm?

o Comparing it with offline algorithm

o The idea is to compute a competitive ratio, which
places an on-line algorithm in competition with an offline algorithm that
receives more information

o An offline algorithm refers to the algorithm that has
access to the entire input from the start and outputs its decision in this
setting. Therefore it’s solution is more optimal than that of online

·
The best
possible competitive ratio for a problem is 1 but may not be 1 even if we use
unlimited computational power due to the lack of information rather than the
lack of computational power.

·

**Concept of Competitive ratio**

The above diagram represents a lost cow problem.

A shortsighted cow is following along an infinite
fence and wants to find the gate. This makes a convenient one-dimensional
planning problem.

If the location of the gate is given, then the cow
can reach it by traveling directly. If the cow is told that the gate is exactly
distance away, then it can move one unit in one direction and return to try the
other direction if the gate has not been found. The competitive ratio in this
case (the set of environments corresponds to all gate placements) is 3

Competitive ratio=cost of online Algo/cost of optimal
Algo i.e. 3/1

**Ski rental problem**

A simple example of an online problem is the
ski-rental problem. A skier can either rent skis for a day or buy them once and
for all. Buying a pair of skis costs k times as much as renting it. Also, skis once bought
cannot be returned. Whenever the skier goes skiing, she does not know whether
she will ski again or how many times. This makes the problem an online one.

Assume that renting skis costs $1 per day and buying
skis costs $10. Every day you have to decide whether to continue renting skis
for one more day or buy a pair of skis. If you know in advance how many days
you will go skiing, you can decide your minimum cost. For example, if you will
be skiing for more than 10 days it will be cheaper to buy skis, while if you
will be skiing for fewer than 10 days it will be cheaper to rent. (If you will
ski for exactly 10 days you are indifferent.) The question is what to do when
you do not know in advance how many days you will ski.

Formally, the problem can be set up as follows. There
is a number of days d (unknown to you) that you will ski. We are looking for an
algorithm that minimizes the ratio between what you pay using the algorithm
(that does not know d) and what you would pay optimally if you knew d in
advance. The problem is generally analyzed in the worst case, where the
algorithm is fixed and then we look at the worst-case performance of the
algorithm over all possible d. In particular, no assumptions are made regarding
the distribution of d (and it is easy to see that, with knowledge of the
distribution of d, a different analysis as well as different solutions would be
preferred).

## The break-even algorithm

The break-even algorithm instructs you to rent for 9
days and buy skis on the morning of day 10 if you are still up for skiing.[4] If you have to stop skiing
during the first 9 days, it costs the same as what you would pay if you had
known the number of days you would go skiing. If you have to stop skiing after
day 10, your cost is $19, which is 90% more than what you would pay if you had
known the number of days you would go skiing in advance. This is the worst case
for the break-even algorithm.

The break-even algorithm is known to be the best
deterministic algorithm for this problem.

- Anonlinestrategywillbeanumberksuch that after renting k-1 times you will buy skis (just before your kth visit).

·
Theorem: Setting
k = y guarantees that you never pay more
than twice the cost of the offline strategy.

·
Proof: when
you buy skis in your kth visit,
even if you quit right after this time, t y.

·
• Yourtotalpaymentisk-1+y=2y-1.

• Theofflinecostismin(t,y)=y.

• Theratiois(2y-1)/y=2-1/y.

• Theofflinecostismin(t,y)=y.

• Theratiois(2y-1)/y=2-1/y.

## 0 comments:

Feel free to contact the admin for any suggestions and help.