4810-1183 Approximation and Online Algorithms with Applications
Lecture Note 7: Online Algorithms for Ski Rental Problem
Ski Rental Problem
At The University of Tokyo, we have a sport facility called “Gotenshita building”. When you arrive atthe building, you can buy a ticket at the automatic machine. There are several types of tickets, but, forsimplicity of this lecture note, let us assume that we only can buy a yearly ticket, which would cost
9,000 yen, and a one-time ticket, which would cost 400 yen.
It is not hard to choose the types of ticket, if we know the number of times we go to the building.
If we go there for less than 9000/400 ≈ 22.5 times, it is more rational to buy the one-time ticket.
Otherwise, we may want to buy the yearly ticket. However, we do not actually know the number oftimes. Everyone believe that they can play sport regularly, but end up going there just for a few times.
We do not know what we will face during a semester.
If we always buy the yearly ticket at the first time, we always have to pay 9,000 yen, no matter
how many times we go there. The worst case is when we go only for one time. While we suppose topay 400 yen, we pay 22.5 times of the optimal payment. We call the gap 22.5 times as competitive ratio.
To be more precise,our payment when we go for 𝐼 days.
𝐼∈ℤ+ possible smallest payment when we go for 𝐼 days

competitive ratio = max

We call a strategy with competitive ratio equals 𝛼 as 𝛼-competitive strategy. So, the strategy of always
buying the yearly ticket at the first time is 22.5-competitive.
Let now slightly change our strategy. We will buy the one-time ticket on the first time, and, if
we go there again, we will buy the yearly ticket. The following graph compares how much we pay andthe smallest payment.

The worst case is clearly when the number of days, denoted by 𝐼, is 2. Under this strategy, we pay 9,400
yen, while the smallest payment is 800 yen. The competitive ratio is then 11.75.
We can see here that, by slightly changing our strategy, we significantly improve thecompetitive ratio by almost half. Let us further modify our strategy. We buy the one-time tickets until
we are at the building for the 23rd time when we buy the yearly ticket. The comparison between ourpayment and the smallest payment is now as in the next page. The worst case is now when 𝐼 = 30. We
pay 17,800 yen, while the smallest payment is 9,000 yen. The competitive ratio becomes 17,800/9,000≈ 1.98.
It is straightforward to show that, for any strategy, we cannot have a smaller competitive ratio
than 17,800/9,000. The strategy in the previous paragraph is the best strategy.

Optimization Model in Online Setting
The problem in the previous section, called ski rental problem, can be formally written by an
optimization model as:
Input:

𝑔1 , … , 𝑔365 ∈ {Yes, No}
𝑔𝑖 = Yes if we go to the Gotenshita Building at day 𝑖

Output:𝑡1 , … , 𝑡365 ∈ {400, 9000, 0}

Constraint:

1) When 𝑔𝑖 = Yes, 𝑡𝑖 = 0 only if 𝑡𝑗 = 9000 for some 𝑗 < 𝑖.
2) 𝑡𝑖 must be decided based on only 𝑔1 , … 𝑔𝑖

Objective Function:

Minimize ∑365
𝑖=0 𝑡𝑖

We usually call an optimization model with the second constraint as an optimization model in online
setting, and we usually call a strategy or an algorithm that is devised for the model as online strategy oronline algorithm.
Competitive Ratio
We can consider our payment as a measurement of how “good” our strategy is. Previously, inapproximation algorithm, we denote the measurement on solution from our algorithm as 𝑆𝑂𝐿, anddenote the measurement on the best solution as 𝑂𝑃𝑇. We will do the same thing here. For a particular
strategy, let us denote our payment on that strategy when we go to Gotenshita for 𝐼 days as 𝑆𝑂𝐿𝐼 , anddenote the possible smallest payment as 𝑂𝑃𝑇𝐼 . By the notation, we have
𝑆𝑂𝐿𝐼,𝐼∈ℤ+ 𝑂𝑃𝑇𝐼

competive ratio = max
competive ratio ≥𝑆𝑂𝐿𝐼
𝑂𝑃𝑇𝐼𝑆𝑂𝐿𝐼 ≤ (competitive ratio) ⋅ 𝑂𝑃𝑇𝐼

for all 𝐼 ∈ ℤ+ ,for all 𝐼 ∈ ℤ+ .

From the above inequality, we know that competitive ratio is actually quite similar to the approximation
ratio. Competitive ratio is for online algorithms, while the approximation ratio is for approximation
algorithms.
In most of the cases, approximation algorithms and online algorithms will not give us 𝑂𝑃𝑇, andtwo of the ratios are not 1. For approximation algorithms, we do not have 𝑂𝑃𝑇 because the problem isnot solvable, but, for online algorithms, it is because we do not have a complete information. While theapproximation ratio is the only way to justify an approximation algorithm, the competitive ratio is not
the only way to justify an online algorithm. We will introduce other ways in the upcoming lecture notes.

Optimal Number of Operating Servers
From now, we will consider the problem proposed in [2]. We are now operating a number of servers,
which will serve a number of demands from users. Servers have operating costs, so we want to havethe smallest number of servers operating. The trivial idea is to have the number of operating servers justequal to the demands. However, the authors found that we have to pay for booting a server. When thenumber of operating servers sharply or frequently increase, the booting cost would be large. Because ofthat, we may want to have a stable number, although that may increase the operating costs. From theconcern, the authors construct the following optimization model
Input:

Demand at each time step 𝑑1 , … , 𝑑𝑛 ∈ ℤ≥0
Operating cost for one server 𝑐𝑂 ∈ ℝ≥0
Booting cost for one server 𝑐𝐵 ∈ ℝ≥0

Output:Number of operating servers 𝑠1 , … , 𝑠𝑛 ∈ ℤ≥0

Constraint:

1) 𝑠𝑖 ≥ 𝑑𝑖2) 𝑠𝑖 must be decided based on only 𝑑1 , … , 𝑑𝑖

Objective Function:

Operating cost is 𝐶𝑂 ≔ 𝑐𝑂 ⋅ ∑𝑛𝑖=1 𝑠𝑖
Booting cost is 𝐶𝐵 ≔ 𝑐𝐵 ⋅ ∑𝑠𝑖−1 <𝑠𝑖 |𝑠𝑖 − 𝑠𝑖−1 |Minimize total cost 𝐶𝑂 + 𝐶𝐵

We have the second constraint because we should not know the future demand. If we do nothave the constraint, we can solve this problem. Let us work on an example to understand thisoptimization in a clearer way.
Example: Suppose that the demands are 𝑑1 = 5, 𝑑2 = 2, and 𝑑3 = 3. The cost for each server 𝑐0 = 1
and 𝑐𝐵 = 2.
If we have the number of operating servers just equal the number required, 𝑠1 = 5, 𝑠2 = 2, 𝑠3 = 3. The
operating cost 𝐶𝑂 is 𝑐𝑜 ⋅ (5 + 2 + 3) = 10. We have to boot 5 servers at the first time step, and oneserver at the third. Because of that, the booting cost is 2 ⋅ (5 + 1) = 12. The total cost is 22.
On the other hand, if we have 𝑠1 = 5, 𝑠2 = 3, 𝑠3 = 3. The operating cost 𝐶𝑂 would become 11, but, as
we do not need to boot the server at the third time step, the booting cost 𝐶𝐵 is 10. We have 𝐶𝑂 + 𝐶𝐵 =21. This output is actually an optimal solution.
Let us try to find an idea for an online algorithm. Consider the situation when we want tocalculate the value of 𝑠𝑖+1 when we have 𝑠1 , … , 𝑠𝑖 and 𝑑1 , … , 𝑑𝑖+1. The calculation would be quite easy
when 𝑑𝑖+1 ≥ 𝑠𝑖 . The only choice for that case would be 𝑠𝑖+1 = 𝑑𝑖+1 . We have to make 𝑠𝑖+1 ≥ 𝑑𝑖+1 ,and, when 𝑠𝑖+1 > 𝑑𝑖+1 , we will spend excessive operating cost and booting cost regardless of what
demands are in future.
When 𝑑𝑖+1 < 𝑠𝑖 , we have to make a decision. The value of 𝑠𝑖+1 can be any number between 𝑠𝑖and 𝑑𝑖+1 . If we have 𝑠𝑖+1 equal to the smallest choice 𝑑𝑖+1 , as in the example, if the demand
immediately raise at the time step 𝑖 + 2 to 𝑠𝑖 + 1, we will have to pay for a larger booting cost than any
other choice. On the other hand, if we have 𝑠𝑖+1 equal to the largest choice, which is 𝑠𝑖 , we will haveto pay a larger operation cost. Especially, if we continue to choose the largest choice for many timesteps and the demand keeps smaller than 𝑠𝑖 , we might end up paying a large operating cost.
When we decide to have 𝑠𝑖 smaller by 1, we may have to pay the booting cost 𝑐𝐵 to restart theserver that we close in future. For simplicity, let us now assume that we always have to pay to bootingcost. Although the cost is actually paid in future, we will now assume that the cost is immediately paid
after 𝑠𝑖 is decreased. After we pay for the booting cost, the number of operating servers will be reduced
by 1. We will not have to pay for the operating cost 𝑐𝑂 . In addition to that, one decrease in the numberof servers can cut the operating cost at more than one time steps. The save in operating cost will be until
we have to raise the number of servers to 𝑠𝑖 .
The discussion in the previous paragraph makes the problem look very similar to the ski rentalproblem. We have to make a decision whether to pay a large cost for one time 𝑐𝐵 or to pay a small costat every time steps. In the ski rental problem, the large cost is the yearly ticket, and the small cost at
every time steps is the one-time ticket.
In the ski rental problem, we will buy the yearly ticket when the amount we pay for the onetime ticket is almost equal to the yearly ticket’s price. For example, for our case for Gotenshita building,the yearly ticket costs 9,000 yen, so we will spend 8,800 = 400 x 22 yen on the one-time ticket. By that,
we will have the smallest competitive ratio, which is 2.
We will apply the same idea to the problems on the operating servers. We will decrease thenumber of servers, when the operating cost of abundant servers is almost equal to the booting cost. The
algorithm for the problem is as follows:
1: For i = 1 to n:
2:
if d[i+1] >= s[i]:3:s[i+1] = d[i+1]4:count[j] = 0 for all j
5:
else:
6:
count[j] += co for all d[i+1] <= j < s[i]7:count[j] = 0 for all other j
8:s[i + 1] = j’ when j’ is smallest j such that count[j] > cb
count[j] will keep track on how much operating cost we spend for not reducing the number of servers

to 𝑗. We will reduce the number of servers to 𝑗 when the counting is larger than the booting cost.
Although we will not prove the following theorem in this lecture note as we to take a lot ofdetail in the proof, one can easily prove it based on the ideas we have discussed so far.
Theorem: The above algorithm is 2-competitive for the optimal number of operating servers problem.
Exercises
In this problem, we will derive an online algorithm for a path finding problem.
Suppose that each dot in the following map is a place that you can try finding a treasure. Two places
are linked together by a line, if you can move between those places. We begin finding a treasure at themiddle of the map, and we want to minimize the number of moves here.

Question 1: If we know that the treasure is at Point 3, how many number of moves we need to get thetreasure?

From next question, assume that there is only one treasure in the map. We know the map, but we do notknow where the treasure is.
Question 2: How many moves do we need to visit all points? How do we move to have that number ofmoves? In that moving method, how many moves until we can find a treasure at Points 2, 4, 6, 8?
Question 3: What is the competitive ratio of your strategy in Question 2?
Question 4: Discuss why there is no strategy of which the competitive ratio is less than 7.
Next, consider the following map, where one link is missing.

Question 5: Find a 7-competitive move strategy for the above map.
Question 6: Discuss why there is no strategy of which the competitive ratio is less than 7 for the above
map. Use the fact that there is no strategy of which the competitive ratio is less than 7 on the firstmap.
In this problem, we will devise an online algorithm for the following situation.
There is a very strange pension system in Country A. Similar to many
countries, when a person turns 60, he/she can choose to receive a lump sum
or a yearly pension. However, there is one different rule. A person who isreceiving the yearly pension can turn to receive the lump sum, but the lumpsum amount will be reduced. The reduction amount is 2 times of the amountthat person has already received as a yearly pension.
For example, assume that the lump sum amount is 80 Million Yen and theyearly pension is 8 Million Yen. If the person choose to receive the yearly
pension at 60 but decide to receive the lump sum at 63, the lump sum
amount that he/she can receive at 63 is80 Million – 2 x (8 Million x 3 Years) = 24 Million.
From next question, assume that the lump sum amount is 80 Million Yen and the yearly
pension is 8 Million Yen.
Question 7: If we know that we live until 99, what is the best strategy for this pension system? Howmuch can we have from the best strategy?
Question 8: If we choose the yearly pension at 60 but turn to choose the lump sum at 63, how much
can we receive if we live until 99?
Question 9: Calculate the competitive ratio of the strategy in Question 8.
Question 10: What is the strategy that maximize the competitive ratio for this situation?
What is the largest competitive ratio?

From next question, assume that the lump sum amount is 𝑋 Million Yen, if a person receive it at 60,
and the yearly pension is 𝑌 Million Yen, when 𝑋 and 𝑌 is given as a known input.
Question 11: Devise a strategy that maximize the competitive ratio for this situation.
What is the largest competitive ratio?
Question 12: Discuss why the idea from Gotenshita (rent-vs-buy) problem discussed in the class does
not work for this problem.
From the following question, instead of considering the competitive ratio, we will consider the expected
income we can receive from the pension system in this problem. By the genome information, we know
the probability that we will die at all specific ages.
In Question 13 – 16, let try to find a strategy that maximize the expected income by the optimization
model.
Question 13: State the input of your optimization model using mathematical formulations.
Question 14: State the output of your optimization model using mathematical formulations.
Question 15: State the constraint of your optimization model using mathematical formulations.
Question 16: State the objective function of your optimization model using mathematical formulations.
Question 17: Devise an efficient algorithm for solving your optimization model.
Question 18: Assume that the lump sum amount is 80 Million Yen, when a person receive it at 60, andthe yearly pension is 8 Million Yen. The probability that the person lives until 𝑥 is 1/40 for all 𝑥 ∈{60, 61, … , 99}. What is the best strategy for this situation? What is the expected income for that beststrategy?
Question 19: The best strategy when we consider competitive ratio is different from the best strategy
when we consider expected income. Discuss when we should use the first strategy, and when we should
use the second strategy.

Reference[1] S. Krumke and C. Thielen, “Introduction to Online Optimization”, Kaiserslautern, 2014.
Chapter 1 http://www.mathematik.uni-kl.de/fileadmin/AGs/opt/Lehre/SS14/Online_SS14/onlineoptimization.pdf[2] M. Lin, A. Wierman, L. Andrew, E. Thereska, “Dynamic right-sizing for power-proportional datacenters”, IEEE/ACM Transactions on Networking (ToN), Vol. 21, No. 5, pages 1378-1391, 2013.