This page is intentionally left blank.
Please do not open this problem sheet until you are told to do so.

4810-1183 Approximation and Online Algorithms with Applications – Final Examination
Problem 1
We discuss randomized rounding in Lecture Note 5. There, you might have a question why we have toset the success probability of each execution to 0.5. In this problem, we will try to set the successprobability in a different way.
From the next question, we will try to have the success probability of each execution equal to 1/|𝐸|.
Question 1.1: When we execute the randomized rounding algorithm for 𝑛 times, what is the probabilityof having at least one execution being successful?
Question 1.2: From Question 1.1, discuss why, when 𝑛 = 50|𝐸| , the success probability of thealgorithm is as small as 1 − 𝑒 −50.
Question 1.3: Calculate the time complexity of the randomized rounding when 𝑛 = 50|𝐸|. Discuss why
our algorithm is still efficient there.
Question 1.4: When we set 𝑥𝑖′ = 1 with probability 1 − (1 − 𝑥𝑖 )𝑡 , calculate the appropriate value of 𝑡.
Question 1.5: What is the expected value of 𝑆𝑂𝐿 in this case?
Question 1.6: Discuss why the approximation result we have in this case is not that better than what wehave in the lecture note.
Question 1.7: Discuss why we cannot have an approximation scheme (guess lecture) by just increasing
the value of 𝑛.

Problem 2
In the problem statement of the 𝑘-center problem (Lecture Note 6), we assume triangle inequality, i.e.,
for all houses 𝑖, 𝑗, 𝑗′, we have 𝑑(𝑖, 𝑗′) ≤ 𝑑(𝑖, 𝑗) + 𝑑(𝑗, 𝑗 ′ ). We will consider the case that we do not havethat assumption in this problem.
Question 2.1: In the lecture note, we assume that there is a library for the 1.9999-approximation 𝑘center problem and use the library to solve the dominating set problem. There, the distance 𝑑 that wesend to the 𝑘-center library is as follows:
0 𝑖𝑓 𝑖 = 𝑗𝑑(𝑖, 𝑗) = {1 𝑖𝑓 {𝑖, 𝑗} ∈ 𝐸
2 Otherwise
Discuss why this distance satisfies the triangle inequality.
Question 2.2: Now, let us consider the following distance.
0 𝑖𝑓 𝑖 = 𝑗𝑑(𝑖, 𝑗) = {1 𝑖𝑓 {𝑖, 𝑗} ∈ 𝐸
3 Otherwise
If we use that in the algorithm for the dominating set problem in lecture note 6, what is the value of 𝐷𝑆 ′when 𝑆′ is a dominating set? And, what is the value of 𝐷𝑆 ′ when 𝑆 ′ is not a dominating set?
Question 2.3: Discuss why, if we can solve 2.9999-approximation 𝑘-center problem, we can solve thedominating set problem by updating the distance 𝑑 as in Question 2.2.

Question 2.4: From your answer in Question 2.3, discuss why, if we do not assume triangle inequality,
we are unlikely to have a 2.9999-approximation algorithm for the 𝑘-center problem.
Question 2.5: Discuss why, if we do not assume triangle inequality, we are unlikely to have an 𝛼approximation algorithm for the 𝑘-center problem for any 𝛼 > 0.

Problem 3
In the machine learning online algorithm that we have discussed in Lecture Note 9, we try to minimize
the number of incorrect decision. However, each incorrect decision cost us a different amount of money.
For example, let us suppose that the stock price falls 300 dollars on day 1 and 1000 dollars on day 3.
Incorrect decisions of buying day 1 and day 3 choose be considered differently. We should try tominimize the sum of money lost by incorrect decisions.
Let us suppose that the amount of money lost must always be a positive integer.
Question 3.1: Formulate the online problem for the above setting by modifying the problem stated inLecture Note 9. What are inputs, outputs, objective function, and constraints?
From the next question, let assume that a lost on a day is at least 𝑝 and at most 𝑃.
Question 3.2: Discuss why we will lose at least 𝑝𝑚 if we know from the beginning who is the bestexpert.
Question 3.3: Discuss why we will lose at most 2.41(𝑚 + lg 2 𝑛) ⋅ 𝑃 by using the weighted majority
voting in lecture note 9.
Question 3.4: What is the competitive ratio of the algorithm for this setting?
Question 3.5: We will modify the algorithm in this question. Instead of decreasing a weight of experts
who makes an incorrect suggestion by half, we will reduce their weight by 1/2𝑝 when 𝑝 is the lost on
the day he/she makes an incorrect suggestion. Give an example that the lost for the modified algorithm
is larger than 2.41(𝑚 + lg 2 𝑛).