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

4810-1185 Network Optimizations – Final Examination 2018
Problem 1
Consider a monotone submodular 𝑓. We will work on some properties of the function in this problem.
Question 1.1: Consider a positive real number 𝑐 and a function 𝑔 such that 𝑔(𝑆) = 𝑐 ⋅ 𝑓(𝑆). Discuss
why 𝑔 is also a monotone submodular function.
Question 1.2: Consider a function 𝑔 such that 𝑔(𝑆) = log 𝑓(𝑆). Discuss why 𝑔 is also a monotone
submodular function.
Question 1.3: Consider a monotone concave function 𝑔. Discuss why ℎ = 𝑔°𝑓 is also a monotone
submodular function.
Question 1.4: Consider a monotone submodular 𝑔. Discuss why ℎ = 𝑔 ⋅ 𝑓 (e.g. ℎ(𝑆) = 𝑔(𝑆) ⋅ 𝑓(𝑆)) isa monotone submodular function.
Question 1.5: Consider a monotone submodular 𝑔. Discuss why ℎ = 𝑔 + 𝑓 (e.g. ℎ(𝑆) = 𝑔(𝑆) + 𝑓(𝑆))is a monotone submodular function.

Problem 2
In this question, we will solve the maximum lifetime coverage problem for the following instance.

Question 2.1: Give ideas how all the target coverages look like.
Question 2.2: Give ideas how the linear program which we use to solve the instance looks like.
Question 2.3: Give ideas how the dual program of your LP in Question 2.2 looks like.
Question 2.4: Discuss why the target coverage {1,2,3} will never been selected in the Garg-Konemann
Framework.
Question 2.5: Consider a target coverage 𝑆 such that there is another target coverage 𝑆′ where 𝑆 ′ ⊆ 𝑆.
Discuss why the target coverage 𝑆 will never been selected in the Garg-Konemann framework.
Question 2.6: From the viewpoint of the Garg-Konemann framework, discuss why we can exclude thetarget coverages in Question 2.5 from our LP.
Question 2.7: From the problem statement of the maximum lifetime coverage problem, discuss why itdoes make sense not to use target coverages in Question 2.5.

4810-1185 Network Optimizations – Final Examination 2018
Problem 3
Consider the following room where there are two routers at corners of the room.

From the following question, assume that there is only one mobile in this room. The approximateddistance from the mobile to both of the routers is 2m.
Question 3.1: Without consider the semi-definite programming in the class, specify what the objectivefunction for this instance is.
Question 3.2: Specify what the solution we expect to have from your objective function in Question 3.1.
Now, assume that there are two mobiles in this room. The approximated distance from both of themobiles to both of the routers is 2m. Also, the approximated distance between both of the mobiles is2m.
Question 3.3: Without consider the semi-definite programming in the class, specify what the objectivefunction for this instance is.
Question 3.4: Guess what the solution we expect to have from your objective function in Question 3.3.
Now, assume that there are 𝑛 mobiles in this room. The approximated distance from all of the mobiles
to both of the routers is 2m. Also, the approximated distance between all mobiles is 2m.
Question 3.5: Guess what the solution we expect to have for this situation.
Question 3.6: Discuss why the solution of the localization problem does not change upon the scalingon the input, i.e. you will be likely to have the same solution even if you assume that all the distancesin Question 3.5 is 1m or 1cm.