Problem 2 - Online Algorithm (10pts) A popular example of the design of an on-line algorithm...

Transcribed Image Text:

Problem 2 - Online Algorithm (10pts) A popular example of the design of an on-line algorithm to minimize the competitive ratio is the ski-buying problem. Suppose you can buy skis for $100, or you can rent skis for $10 per day. You decide to take up skiing, but you don't know if you will like it. You may try skiing for any number of days and then give it up. The merit of an algorithm is the cost per day of skis, and we must try to minimize this cost. One on-line algorithm for making the rent/buy decision is “buy skis immediately." If you try skiing once, fall down and give it up, then this on-line algorithm costs you $100 per day, while the optimum off-line algorithm would have you rent skis for $10 for the one day you used them. Thus, the competitive ratio of the algorithm “buy skis immediately” is at most , and that is in fact the exact competitive ratio, since using the skis one day is the worst possible outcome for this algorithm. On the other hand, the on-line algorithm "always rent skis” has an arbitrarily small competitive ratio. If you turn out to really like skiing and go regularly, then after n days, you will have paid $10n or $10/day, while the optimum off-line algorithm would have bought skis at once, and paid only $100. The competitive ratio can be arbitrarily small, which is 100 10-n Your question: design an on-line algorithm for the ski-buying problem that has the best possible competitive ratio. What is that competitive ratio? Hints: In the problem description, the competitive ratios of two example online algo- rithms were analyzed: (1) the online algorithm "buy skis immediately". For this algorithm, the worst case is when you ski only once and then give up. In that case, the competitive ratio (in this worst scenario of this online algorithm) is 10/100 (2) the online algorithm "always rent". For this algorithm, the worst case scenario is when you ski regularly for many times, let's say n times and n >> 10. In that case, the competitive ratio (in the worst scenario when n >> 10), the competitive ratio can be arbitrarily small, which is 100/10n The problem in the description asks you to design an online algorithm, which is different from (1) and (2), so that it has the best possible (i.e. maximum) competitive ratio. When designing the algorithm, you should take into consideration the one input that is available to you, t, which is the number of times you have previously gone skiing. For instance, you can design algorithms like, "buy skis after having gone skiing a number of times", where x is a variable. And you need to answer what the value of a should be, for that online algorithm to have maximum competitive ratio. Please include in your solution the analysis of competitive ratio for different values of x. Problem 2 - Online Algorithm (10pts) A popular example of the design of an on-line algorithm to minimize the competitive ratio is the ski-buying problem. Suppose you can buy skis for $100, or you can rent skis for $10 per day. You decide to take up skiing, but you don't know if you will like it. You may try skiing for any number of days and then give it up. The merit of an algorithm is the cost per day of skis, and we must try to minimize this cost. One on-line algorithm for making the rent/buy decision is “buy skis immediately." If you try skiing once, fall down and give it up, then this on-line algorithm costs you $100 per day, while the optimum off-line algorithm would have you rent skis for $10 for the one day you used them. Thus, the competitive ratio of the algorithm “buy skis immediately” is at most , and that is in fact the exact competitive ratio, since using the skis one day is the worst possible outcome for this algorithm. On the other hand, the on-line algorithm "always rent skis” has an arbitrarily small competitive ratio. If you turn out to really like skiing and go regularly, then after n days, you will have paid $10n or $10/day, while the optimum off-line algorithm would have bought skis at once, and paid only $100. The competitive ratio can be arbitrarily small, which is 100 10-n Your question: design an on-line algorithm for the ski-buying problem that has the best possible competitive ratio. What is that competitive ratio? Hints: In the problem description, the competitive ratios of two example online algo- rithms were analyzed: (1) the online algorithm "buy skis immediately". For this algorithm, the worst case is when you ski only once and then give up. In that case, the competitive ratio (in this worst scenario of this online algorithm) is 10/100 (2) the online algorithm "always rent". For this algorithm, the worst case scenario is when you ski regularly for many times, let's say n times and n >> 10. In that case, the competitive ratio (in the worst scenario when n >> 10), the competitive ratio can be arbitrarily small, which is 100/10n The problem in the description asks you to design an online algorithm, which is different from (1) and (2), so that it has the best possible (i.e. maximum) competitive ratio. When designing the algorithm, you should take into consideration the one input that is available to you, t, which is the number of times you have previously gone skiing. For instance, you can design algorithms like, "buy skis after having gone skiing a number of times", where x is a variable. And you need to answer what the value of a should be, for that online algorithm to have maximum competitive ratio. Please include in your solution the analysis of competitive ratio for different values of x.

Answer rating: 100% (QA)

To design an online algorithm for the skibuying problem with the best ie smallest maxi... View the full answer