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.