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

4810-1183 Approximation and Online Algorithms with Applications
Midterm Problem 1
In Lecture Note 2, we have discussed the product selection problem. There, we tried to maximize
the number of customers who choose the products that we will propose. You might think that theobjective function is not very practical. Companies may not want to maximize the number ofcustomers but the revenue they will have. In this problem, you will modify the optimization model
discussed in the class to maximize the revenue, which is the sum of prices of the products that arebought by our customers.
Question 1.1: State an input of your optimization model by a mathematical formulation.
Question 1.2: State an output of your optimization model by a mathematical formulation.
Question 1.3: State an objective function of your optimization model by a mathematicalformulation.
Question 1.4: State a constraint of your optimization model by a mathematical formulation.
Recall that the 𝑘-most representative skyline operator problem introduced in Lecture 2 is an NPhard problem.
Question 1.5: Assume that there is a library for your optimization model providing in the internet.
Use that library to write a program for the k-most representative skyline operator problem.
AnswerOf1.2 yourOptimizationModel(Answer of 1.1);
Set kMostRepresentativeSkyline(Vectors P, Vectors C, int k){//Your code go here.
}

Question 1.6: Discuss why, by Question 1.5, your optimization model is unlikely solvable?
Question 1.7: Can you show that your optimization model is NP-hard based on the fact that theproduct selection problem is NP-hard? If yes, show it. Otherwise, give a reason why you cannot
do that.

4810-1183 Approximation and Online Algorithms with Applications
Midterm Problem 2
In this problem, we will try to find a set of numbers such that the sum of their squares is closest
to a given integer. For example, if the input is 13, the output should be 2, 3 as 22 + 32 = 13.
Consider the following optimization model. We will call the model as Model 1.
Input:

An integer 𝑛

Output:Set of positive number 𝑆

Objective Function:

Maximize 𝑛 − |𝑛 − ∑𝑖∈𝑆 𝑖 2 |Question 2.1: Discuss why an optimal solution of the optimization model is a set of numbers thatthe sum of their squares is closest to 𝑛.
We change the optimization model to the following. We call it Model 2.
Input:

Weight of 𝑖 ∈ {1, … 𝑛}, 𝑤𝑖 = 𝑖 2 , integer 𝑊 = 𝑛

Output:Set of positive number 𝑆

Constraint:∑𝑖∈𝑆 𝑤𝑖 ≤ 𝑊

Objective Function:

Maximize ∑𝑖∈𝑆 𝑖 2Question 2.2: Give one input such that the optimal value of Model 1 is different from the optimalvalue of Model 2.
As Model 2 is the simplified version of the knapsack problem in Lecture Note 1, from the nextquestions, we will use the 2-approximation algorithm for the knapsack problem on the problem.
Question 2.3: What is the output of the approximation algorithm when 𝑊 = 13 and 𝑊 = 15?
Question 2.4: Discuss why the output is either in the form of {1, … , 𝑘} or {𝑘 + 1} for some 𝑘.
From the next question, we will use the fact that 12 + ⋯ + 𝑘 2 > (𝑘 + 1)2 for all 𝑘 ≥ 4.
Question 2.5: Discuss why the output is always in the form of {1, … , 𝑘} for all 𝑛 > 25.
Question 2.6: Give a 2-approximation algorithm for Model 1.

4810-1183 Approximation and Online Algorithms with Applications
Midterm Problem 3
In Lecture Note 1, we have a language ability of all students, denoted by ℓ𝑖 for student 𝑖, andwe try to increase an ability of all students to make sure that, for all students 𝑖 and 𝑗,ℓ𝑖 + ℓ𝑗 ≥ 5.
We turn to believe that the communication is not always between just two persons.
Group works are also very important. We want to make sure that every groups of 3 students haveenough communication skills to work together. Let us say that the minimum sum skills for a groupof 3 is 7, so we want to have, for all students 𝑖, 𝑗,and 𝑘, ℓ𝑖 + ℓ𝑗 + ℓ𝑘 ≥ 7.
Again, we have to pay to increase the language ability. If we increase the ability of a
student from ℓ𝑖 to ℓ′𝑖 , the cost for the student will be 10000 ⋅ (ℓ′𝑖 − ℓ𝑖 ). The cost that we haveto pay is then equal to ∑𝑖[10000 ⋅ (ℓ′𝑖 − ℓ𝑖 )].
Question 3.1: Write an optimization for this problem.
From next question, we will try to solve this problem by an algorithm for the linear programming.
Please note that ℓ𝑖 is not integer but real number.
Question 3.2: Describe how you construct a matrix 𝑨 to give as an input of the algorithm.
(Just explaining an idea or giving a code would be enough.)
Question 3.3: Describe how you construct a vector 𝒃 to give as an input of the algorithm.
Question 3.4: Describe how you construct a vector 𝒄 to give as an input of the algorithm.
Question 3.5: Describe how you translate a vector 𝒙 given from the algorithm as an output ofyour optimization model.