4810-1183 Approximation and Online Algorithms with Applications
Lecture Note 6: Inapproximability
Introduction
When we work on approximation algorithm, we want to find an algorithm of which the approximation
ratio is close to 1 (0.99999 for maximization problem and 1.00001 for minimization problem). However,for the vertex cover problem, we have a 2-approximation algorithm. Other researchers might havequestions if you can have a better approximation ratio for the problem. They might try to beat you byfinding a 1.9999-approximation algorithm for the problem. However, it might be impossible to havethat. Those researchers may waste time, but cannot find anything.
In Lecture 2, we discuss “NP-hardness”, which how to prove that a problem is not solvable.
We will use the concept to formally show that 1.9999-approximation algorithm for vertex cover is notpossible in this lecture note.
Reformulating Problems
Recall that the formulation of the vertex cover problem is as follows:
Input:

Set 𝑉, Set 𝐸 ⊆ {{𝑢, 𝑣}: 𝑢, 𝑣 ∈ 𝑉}

Output:𝑆⊆𝑉

Constraint:

For all {𝑢, 𝑣} ∈ 𝐸, 𝑢 ∈ 𝑆 or 𝑣 ∈ 𝑆

Objective Function:

Minimize |𝑆|

We want to find a valid set 𝑆 that is smaller than any valid set 𝑆 ′ . In other word, if 𝑆 is an optimal
solution of the optimization model, |𝑆| ≤ |𝑆 ′ | for all 𝑆 ′ that satisfies the constraint. We can replace theobjective function with the following constraint.
Input:

Set 𝑉, Set 𝐸 ⊆ {{𝑢, 𝑣}: 𝑢, 𝑣 ∈ 𝑉}

Output:𝑆⊆𝑉

Constraint:

For all {𝑢, 𝑣} ∈ 𝐸, 𝑢 ∈ 𝑆 or 𝑣 ∈ 𝑆.
For all 𝑆 ′ such that, for all {𝑢, 𝑣} ∈ 𝐸, 𝑢 ∈ 𝑆 or 𝑣 ∈ 𝑆, we have |𝑆| ≤ |𝑆 ′ |Objective Function:

None

All solutions of the new problem are optimal solutions of vertex cover. When we have an 1.9999approximation algorithm for vertex cover, it means that, from the algorithm, we have 𝑆 such that |𝑆| ≤1.9999 ⋅ 𝑂𝑃𝑇. Because 𝑂𝑃𝑇 is the smallest size of all the valid 𝑆 ′ , we know that the above inequality
is equivalent to |𝑆| ≤ 1.9999 ⋅ |𝑆 ′ | for all valid 𝑆 ′ .
As a conclusion of the discussion in the previous paragraph, if we have an 1.9999approximation algorithm for vertex cover, we can solve the following optimization model. On the other
hand, if we can solve the optimization model, we will have an 1.9999-approximation algorithm. We
will call the model as 1.9999-approximation vertex cover problem.
Input:

Set 𝑉, Set 𝐸 ⊆ {{𝑢, 𝑣}: 𝑢, 𝑣 ∈ 𝑉}

Output:𝑆⊆𝑉

Constraint:

For all {𝑢, 𝑣} ∈ 𝐸, 𝑢 ∈ 𝑆 or 𝑣 ∈ 𝑆.
For all 𝑆 ′ such that, for all {𝑢, 𝑣} ∈ 𝐸, 𝑢 ∈ 𝑆 or 𝑣 ∈ 𝑆,
we have |𝑆| ≤ 1.9999 ⋅ |𝑆 ′ |Objective Function:

None

Having the 1.9999-approximation algorithm is as hard as solving the 1.9999-approximation vertex
cover problem. If the solving the problem is not possible, then having the 1.9999-approximation
algorithm is also not possible. To show that solving the problem is not possible, we can prove that the
problem is NP-hard.
Inapproximability of the Vertex Cover Problem
Unfortunately, no one can prove that the 1.9999-approximation vertex cover problem is NP-hard. On
the other hand, no one can find a 1.9999-approximation algorithm for the vertex cover problem. Becauseof that, the smallest approximation ratio is still an open problem.
Recall that we believe that NP-hard problems are not solvable based on our belief that SAT is
not solvable. There is some people believe that, not only SAT is not solvable, but some problems easierthan SAT are also not solvable. Two of the most well-known examples are called as unique games
conjecture, which believe that a problem called unique game is not solvable, and exponential-time
hypothesis, which believe that we cannot solve SAT in 𝑂(1.9999𝑛 ) . We know that a 1.9999approximation algorithm for the vertex cover is not possible under the unique games conjecture.
Warm up
When a 1.9999-approximation algorithm for vertex cover is not possible, we know that 1.5approximation algorithm is also not possible. However, let try to show that systematically.
We know that having a 1.9999-approximation algorithm is equivalent to solving the 1.9999approximation vertex cover problem. Using the same argument, we know that having a 1.5approximation algorithm is equivalent to the following model, called as 1.5-approximation vertex coverproblem.
Input:

Set 𝑉, Set 𝐸 ⊆ {{𝑢, 𝑣}: 𝑢, 𝑣 ∈ 𝑉}

Output:𝑆⊆𝑉

Constraint:

For all {𝑢, 𝑣} ∈ 𝐸, 𝑢 ∈ 𝑆 or 𝑣 ∈ 𝑆.
For all 𝑆 ′ such that, for all {𝑢, 𝑣} ∈ 𝐸, 𝑢 ∈ 𝑆 or 𝑣 ∈ 𝑆,
we have |𝑆| ≤ 1.5 ⋅ |𝑆 ′ |Objective Function:

None

We will prove that the 1.5-approximation vertex cover is not solvable, based on the fact that 1.9999approximation vertex cover is not solvable. In other words, we will show that the 1.5-approximation
vertex cover is harder than the 1.9999-approximation vertex cover.
To do that, we will assume that there is an algorithm for the 1.5-approximation vertex coverprovided in a library. Then, we will write a program for the 1.9999-approximation vertex cover. Thatis:Set 1.5ApproxVertexCover(Set V, Set E)
Set 1.9999ApproxVertexCover(Set V, Set E){
return 1.5ApproxVertexCover(V, E)}

Let us discuss why the above program for 1.9999ApproxVertexCover is valid. From thefunction 1.5ApproxVertexCover, we have the output 𝑆 such that |𝑆| ≤ 1.5|𝑆 ′ | for all valid 𝑆 ′ . Thatmeans 𝑆 is a set such that |𝑆| ≤ 1.5|𝑆 ′ | ≤ 1.999|𝑆 ′ | for all valid 𝑆 ′ , and 𝑆 is also a solution for1.9999ApproxVertexCover.
We

can

solve

1.5ApproxVertexCover

1.9999ApproxVertexCoverusing 1.5ApproxVertexCover.
is harder than 1.9999ApproxVertexCover. When the 1.9999-

approximation vertex cover problem is not solvable, the 1.5-approximation vertex cover problem is also
not solvable.
𝒌-Center Problem
Called as “clustering”, dividing a set of information to groups are one of basic problems in machinelearning. However, the word “clustering” is not formally defined. There are many works trying toformalize clustering into optimization models. Two of the most well-known formulation are “𝑘-means”
and “𝑘-center”. We will focus on the 𝑘-center, which is formulated below, in this lecture note.
Input:

Number of data points 𝑛
For all 𝑖, 𝑗, distance between 𝑖 and 𝑗 denoted by 𝑑(𝑖, 𝑗)
Assumption: for all 𝑖, 𝑗, 𝑗′, 𝑑(𝑖, 𝑗) ≤ 𝑑(𝑖, 𝑗 ′ ) + 𝑑(𝑗 ′ , 𝑗)
Number of groups to find 𝑘

Output:Positions of centers for each group 𝑆 ⊆ {1, … , 𝑛}Constraint:|𝑆| = 𝑘Objective Function:

Distance to closest center of 𝐱𝑖 is 𝑑𝑖 = min 𝑑(𝑖, 𝑗)𝑗∈𝑆

Minimize max 𝑑𝑖𝑖

To understand the formulation, let us consider the case that we have 𝑛 houses in our city. Theirlocations are 𝐱1 , … , 𝐱𝑛 . We want to set up 𝑘 ward offices in the city, and we want to minimize thecommuting time from houses to ward office. We believe that each house will commute to the closest
office, and their commuting distance would be 𝑑𝑖 . The most suffering house is going to be a house withthe largest 𝑑𝑖 , i.e. a house with commuting time equals max 𝑑𝑖 . We want to having the most suffering𝑖house has the least suffer as possible, so we minimize max 𝑑𝑖 .
𝑖Houses will be put to the same group if they use the same ward office. Consider a city with 7
houses. The locations of the houses is shown below. Suppose that we set the ward offices at position
𝑆 = {3,5}. All houses can commute to ward offices within distance √2. We know that {3,5} is the
optimal solution for this input. Houses that will go to the ward office located at 𝐱 3 is 1,2,3, while houses
that will go to the ward office located at 𝐱5 is 4, 5, 6, 7. By that, we can divide the houses (data) into 2
groups {1,2,3} and {4,5,6,7}.

There is a 2-approximation algorithm for the 𝑘-center formulation [1]. The algorithm is basedon the greedy scheme that we discussed in lecture note 3. In this lecture note, we will show that a
1.9999-approximation algorithm is not possible. That is equivalent to showing that the following
optimization model is not solvable.
Input:

Number of data points 𝑛
For all 𝑖, 𝑗 ∈ {1, … , 𝑛}, distance between 𝑖 and 𝑗 denoted by 𝑑Assumption: For all 𝑖, 𝑗, 𝑗′, 𝑑(𝑖, 𝑗) ≤ 𝑑(𝑖, 𝑗 ′ ) + 𝑑(𝑗 ′ , 𝑗)
Number of groups to find 𝑘

Output:Positions of centers for each group 𝑆 ⊆ {1, … , 𝑛}Constraint:|𝑆| = 𝑘For any set 𝑆, suppose that 𝐷𝑆 ≔ max min′ ||𝐱𝑖 − 𝐱𝑗 ||.
𝑖∈{1,…,𝑛} 𝑗∈𝑆′

For any 𝑆 such that |𝑆 ′ | = 𝑘, 𝐷𝑆 ≤ 1.9999 ⋅ 𝐷𝑆 ′Objective Function:

None

We will call the problem as 1.9999-approximation 𝑘-center problem. From now, we will prove that the
problem is NP-hard. The proof will based on the fact that the dominating set, defined in the following
section, is NP-hard.
Dominating Set Problem
We will turn back to a problem on social networks. Previously, in the vertex cover problem, we choose
a set of persons to cover all communications (friendships). In dominating set problem, we want to cover
all persons. In other words, every persons must be in the set or next to someone in the set.
Consider a social network with a set of persons 𝑉 and a set of friendships 𝐸 ⊆ {{𝑢, 𝑣}: 𝑢, 𝑣 ∈ 𝑉}.
A set 𝑆 ⊆ 𝑉 is a dominating set of the social network, if all 𝑣 ∈ 𝑉 satisfy one of the following
conditions:
1. 𝑣 ∈ 𝑆
2. There is 𝑢 such that 𝑢 ∈ 𝑆 and {𝑢, 𝑣} ∈ 𝐸.
In the below social network, {𝐴, 𝐸} is not a dominating set, as 𝐶 is not in the set and {𝐴, 𝐸} do not havea friendship with 𝐶. On the other hand, {𝐵, 𝐷} is a dominating set, as {𝐵, 𝐷} are friends of everyone in
the social network.

The formulation of the dominating set problem is as follows. The dominating set problem is
one of the most NP-hard problem.
Input:

Set 𝑉, Set 𝐸 ⊆ {{𝑢, 𝑣}: 𝑢, 𝑣 ∈ 𝑉}
Positive integer 𝑘

Output:Yes or No

Constraint:

Yes, if there is a dominating set 𝑆 with |𝑆| ≤ 𝑘.
No, otherwiseObjective Function:

None

Inapproximability of the 𝒌-center Problem
Now, we are ready to prove that the 1.9999-approximation 𝑘-center problem is NP-hard. We will provethat the problem is harder than the dominating set problem, which is NP-hard. Thus, we will assume
that a program for the 1.9999-approximation 𝑘-center problem is provided in a library, and we will
write a program for the dominating set problem based on that.
A program for the dominating set problem is as follows:Set 1.9999ApproxKCenter(int n, double[][] d, int k);boolean dominatingSet(Set V, Set E, k){
Suppose that 𝑉 = {1, … , 𝑛}
Let 𝑑 be a 2-dimenstional array with size 𝑛 × 𝑛.
0
when 𝑖 = 𝑗𝑑[𝑖][𝑗] = {1 when {𝑖, 𝑗} ∈ 𝐸
2otherwise.
𝑆 ′ = 1.9999ApproxKCenter(n, d, k)
If 𝐷𝑆 ′ ≤ 1:
return Yes
Else:return No}

When there exists a dominating set 𝑆 with |𝑆| = 𝑘, all persons are in 𝑆 or have friends in 𝑆. By
the definition of 𝑑[𝑖][𝑗] in the program, for all persons 𝑖 ∈ 𝑉, there always exists person 𝑗 ∈ 𝑆 such that𝑑[𝑖][𝑗] = 0 or 𝑑[𝑖][𝑗] = 1. As we use 𝑑 as a distance in the 𝑘-center problem, if we set up ward offices
at all houses in 𝑆, we know that the distance from 𝑖 to the closest ward office (𝑗 ∈ 𝑆) would not be morethan 1. We have 𝐷𝑆 = 1.
We know that the output of 1.9999ApproxKCenter, denoted by 𝑆′, has 𝐷𝑆 ′ ≤ 1.9999 ⋅ 𝐷𝑆 =1.9999. As, for this input, 𝐷𝑆 ′ can be only 1 and 2, when 𝐷𝑆 ′ ≤ 1.9999, we know that 𝐷𝑆 ′ = 1. The
output of dominatingSet is Yes as it should be.
When there does not exist a dominating set 𝑆 with |𝑆| = 𝑘, by the same argument, we willknow that all 𝑆 has 𝐷𝑆 = 2. The output of 1.9999ApproxKCenter, denoted by 𝑆′ is then has 𝐷𝑆 ′ =2. The output of dominatingSet is Yes as it should be.
RG-TOSS Problem
In this section, we will consider the robustness guaranteed task-optimized group search (RG-TOSS)
problem. The problem is proposed in [2].
The authors consider “social networks of the Internet of Things (IoTs)”. Mathematically, it isvery similar to ordinary social networks we have discussed so far. The only difference is the set 𝑉 is
not a set of persons, but a set of “anything” (e.g. lights, air conditions, fridges). We have {𝑢, 𝑣} ∈ 𝐸
when 𝑢 and 𝑣 can communicate using any type of networks (4G, Wi-fi).
Let us consider the social network in the following page. In a smart house, we have sensors at
the following 3 furniture, fridge, light, and air condition. To precisely set the power of the air condition,
we want to measure the temperature at three red points. The sensor attached at the fridge can guess thetemperature at point 1 very well, and may be able to measure the temperature at point 2. Suppose thatthe probability that the sensor can have the temperature from point 1 is 0.9 and from point 2 is 0.5.

Suppose that we would like to have the temperature information only at point 1. We cannot
collect the information at all of the sensors as the data collection is costly. We can collect from thesensor at fridge, then we can collect the information with probability 0.9. However, it is possible thatthe information is incorrect. The sensor wants to make sure that what they have got is correct with theirpeers, which are sensors that can directly communicate with them. If we select more sensors aroundthem, the information will be rechecked more, and we will have a robust information.
We will require each selected sensor to be friends of at least 𝑘 selected sensors. For example,
in the above sensor network, we cannot select only the sensor at the fridge but we have to also include
the sensor at the light.
By the discussion, our optimization model, is as follows:
Input:

Set of sensors 𝑉, Set of friendships 𝐸 ⊆ {{𝑢, 𝑣}: 𝑢, 𝑣 ∈ 𝑉}
Set of measurement point 𝑇
For all 𝑡 ∈ 𝑇 and 𝑣 ∈ 𝑉, the probability that we have information 𝑡 by thesensor 𝑣 ∈ 𝑉, denoted by 𝑝(𝑡, 𝑣)
Robustness parameter 𝑘 ∈ ℤ>0 , budget 𝑠 ∈ ℤ>0

Output:𝑆⊆𝑉

Constraint:

For all 𝑣 ∈ 𝑆, |{{𝑢, 𝑣} ∈ 𝐸: 𝑢 ∈ 𝑆}| ≥ 𝑘, |𝑆| = 𝑠

Objective Function:

Maximize ∑𝑡 𝑃(𝑡) when 𝑃(𝑡) ≔ ∑𝑣∈𝑆 𝑝(𝑡, 𝑣) is a probability of having theinformation at the measurement point 𝑡

The optimization model is clearly NP-hard, even to find an output that satisfies the constraint.
Let us now consider the above model when we do not have the objective function. Without the objectivefunction, we do not need to have 𝑇 and 𝑝(𝑡, 𝑣) as our inputs anymore. The optimization model is asfollows:
Input:

Set of sensors 𝑉, Set of friendships 𝐸 ⊆ {{𝑢, 𝑣}: 𝑢, 𝑣 ∈ 𝑉}
Robustness parameter 𝑘 ∈ ℤ>0 , budget 𝑠 ∈ ℤ>0

Output:𝑆⊆𝑉

Constraint:

For all 𝑣 ∈ 𝑆, |{{𝑢, 𝑣} ∈ 𝐸: 𝑢 ∈ 𝑆}| ≥ 𝑘, |𝑆| = 𝑠

Objective Function:

None

We will call the optimization model as RG-TOSS’, and will prove that the problem is NP-hard.
Previously, we introduce you the clique problem. Recall that the optimization model of the problem is
as follows:Input:Set 𝑉, Set 𝐸 ⊆ {{𝑢, 𝑣}: 𝑢, 𝑣 ∈ 𝑉}𝑠 ∈ ℤ>0

Output:𝑆⊆𝑉

Constraint:

For all 𝑢, 𝑣 ∈ 𝑆, {𝑢, 𝑣} ∈ 𝐸, |𝑆| = 𝑠

Objective Function:

None

The input, output, and objective function of the clique problem. The only different is the constraint. Let
us consider the case when 𝑘 = 𝑠 − 1. We have |{{𝑢, 𝑣} ∈ 𝐸, 𝑢 ∈ 𝑆}| ≥ 𝑘 − 1. As |𝑆| = 𝑘, when we
have the constraint, we know that all 𝑢 ∈ 𝑆 − {𝑣} are friends of 𝑣. We know that, for all 𝑢, 𝑣 ∈ 𝑆,{𝑢, 𝑣} ∈ 𝐸, which is a constraint of the clique problem. To conclude, we know that RG-TOSS’ isequivalent to the clique problem when 𝑘 = 𝑠 − 1. We can write a program for the clique problem basedon a library for RG-TOSS’ as follows:
Set RG-TOSS’(Set V, Set E, int k, int s)
Set clique(Set V, Set E, int s){
RG-TOSS’(V, E, s-1, s)}

By the above program, we know that RG-TOSS’ is NP-hard. Even finding a solution is NP-hard, it isstraightforward to show that find a solution that optimize an objective function is also NP-hard.
When it comes to approximation algorithms, things will become more complicated. Previously,
algorithms can find a solution just it is not an optimal, so we can prove that 𝑆𝑂𝐿 ≤ 𝑂𝑃𝑇. We cannot
even find a solution now. The definition of approximation algorithm cannot apply here, because 𝑆𝑂𝐿 isnot very well defined. The authors cope with the problem with the following reformulation.
Input:

Set 𝑉, Set 𝐸 ⊆ {{𝑢, 𝑣}: 𝑢, 𝑣 ∈ 𝑉}
Set 𝑇, for all 𝑡 ∈ 𝑇 and 𝑣 ∈ 𝑉, probability 𝑝(𝑡, 𝑣)
𝑘, 𝑠 ∈ ℤ>0

Output:𝑆⊆𝑉

Constraint:|𝑆| = 𝑠Objective Function:

Maximize 𝐿
𝐿 = 0 when |{{𝑢, 𝑣} ∈ 𝐸: 𝑢 ∈ 𝑆}| < 𝑘.
Otherwise, 𝐿 = ∑𝑡 𝑃(𝑡) when 𝑃(𝑡) ≔ ∑𝑣∈𝑆 𝑝(𝑡, 𝑣)

Personally, I am skeptical on the reformulation, but let us try to discuss the inapproximability of theabove problem, which we will call as RG-TOSS’’.
The authors of [2] show that, for RG-TOSS’’, it is not possible to have 𝛼-approximation
algorithm for any 𝛼 > 0. To prove that, we have to reformulate the problem. Let 𝐿𝑆 be the value of 𝐿
we will have for a set 𝑆. We will reformulate RG-TOSS’’ to the optimization model.
Input:

Set 𝑉, Set 𝐸 ⊆ {{𝑢, 𝑣}: 𝑢, 𝑣 ∈ 𝑉}
Set 𝑇, for all 𝑡 ∈ 𝑇 and 𝑣 ∈ 𝑉, probability 𝑝(𝑡, 𝑣)
𝑘, 𝑠 ∈ ℤ>0

Output:𝑆⊆𝑉

Constraint:|𝑆| = 𝑠𝐿𝑆 ≤ 𝐿𝑆 ′ for all 𝑆 ′ ⊆ 𝑉 such that |𝑆 ′ | = 𝑠.

Objective Function:

None

Having 𝛼-approximation algorithm is as hard as solving the following optimization model.
Input:

Set 𝑉, Set 𝐸 ⊆ {{𝑢, 𝑣}: 𝑢, 𝑣 ∈ 𝑉}
Set 𝑇, for all 𝑡 ∈ 𝑇 and 𝑣 ∈ 𝑉, probability 𝑝(𝑡, 𝑣)
𝑘, 𝑠 ∈ ℤ>0

Output:𝑆⊆𝑉

Constraint:|𝑆| = 𝑠𝐿𝑆 ≤ 𝛼 ⋅ 𝐿𝑆 ′ for all 𝑆 ′ ⊆ 𝑉 such that |𝑆 ′ | = 𝑠.

Objective Function:

None

By the definition of 𝐿𝑆 , when 𝑠 = 𝑘 − 1, 𝐿𝑆 = 0 for all non-clique 𝑆. When 𝑆 is a solution of the clique
problem, we have 𝐿𝑆 > 0. By the following program, we will prove that above optimization model,
called as 𝛼-approximation RG-TOSS’’ is NP-hard based on the fact that the clique problem is NP-hard.
Set alpha-approx-RG-TOSS’’(Set V, Set E, int k, int s)
Set clique(Set V, Set E, int s){
return alpha-approx-RG-TOSS’’(V, E, s-1, s)}

Suppose that there exists a clique 𝑆 ′ with |𝑆 ′ | = 𝑠. We know that there is some 𝑆 ′ such that
|𝑆 ′ | = 𝑠 and 𝐿𝑆 ′ > 0. Let us assume that the output of alpha-approx-RG-TOSS’’ is 𝑆. By theconstraint of the 𝛼-approximation RG-TOSS’’, we have 𝐿𝑆 ≥ 𝛼 ⋅ 𝐿𝑆 ′ . As 𝛼 > 0 and 𝐿𝑆 ′ > 0, 𝐿𝑆 > 0.
𝑆 is a clique and the function clique runs correctly.
We then know that it is not possible to have any approximation algorithm for the RG-TOSS’’
problem.
Exercises
Consider the following optimization model:
Input:𝒜

Output:ℬ

Constraint:𝒞

Objective Function:

Maximize 𝒟

We assume that, for any output that satisfies the constraint 𝒞, the objective value 𝒟 is non-negative. Let
us call the above optimization model as Problem 1.
Question 1: Define an optimization model that is as hard as having a 0.5-approximation algorithm for
Problem 1.
From now, we will assume that it is not possible to have a 0.5-approximation algorithm for Problem 1.
Let us recall an optimization model with the same input, output, and constraint, but with the following
objective function.
Objective Function:

Minimize 1/𝒟

We will call the optimization model as Problem 2.

Question 2: Define an optimization model that is as hard as having a 2-approximation algorithm for
Problem 2.
Question 3: Assume that there is a problem for your optimization model in Question 2. Write a program
to solve an optimization model in Question 1. Discuss why your program works.
Question 4: Based on your answer in Question 3, discuss why it is not possible to have a 2approximation algorithm for Problem 2.
From the following question, let us assume that, for any output that satisfies the constraint 𝒞, theobjective value 𝒟 is between 0 and 1. Consider Problem 3 with the same input, output, and objectivefunction, but with the following objective function.
Objective Function:

Minimize 1 − 𝐷

Question 5: Assume that we have a 2-approximation algorithm for problem 3. If we use that algorithm
for Problem 1, what are the guarantees on the outputs’ objective values when the optimal value (ofProblem 1) are 0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, and 2.
Question 6: Based on your answer in Question 5, discuss why knowing that “an 𝛼-approximation
algorithm is not possible for problem 1” does not help us showing that “an 𝛼 ′ -approximation algorithm
is not possible for problem 3”.
Consider the following situation.
In 𝑘-center problem, we have a set of positions for 𝑛 houses. Out of that𝑛 houses, we will pick to install ward offices at 𝑘 houses, and minimize thelongest commute time from houses to ward offices. In our discussion, we
assume that the commute time is proportional to the Euclidean distance, i.e.
if the Euclidean distance is 𝑑 the commute time is 𝑐 ⋅ 𝑑 for some constant 𝑐.
For this problem, we will consider the setting where we have somedisabilities in our city. Instead of 𝑐 ⋅ 𝑑 like others, the disabilities will take2 ⋅ 𝑐 ⋅ 𝑑 to get to a ward office with Euclidean distance 𝑑. With thosedisabilities, we still want to minimize the longest commute time fromhouses to ward offices.
We will call this problem as 𝑘-center with disabilities.
Question 7: State inputs of this problem by a mathematical formulation.
Question 8: State outputs of this problem by a mathematical formulation.
Question 9: State constraints of this problem by a mathematical formulation.
Question 10: State objective functions of this problem by a mathematical formulation.
Question 11: State constraints of 1.999-approx 𝑘-center with disabilities.
Question 12: Write a program for solving 1.999-approx 𝑘-center based on the assumption that an
efficient algorithm for solving the 1.999-approx 𝑘-center with disabilities problem is given in alibrary.
[AnswerOf1_2] 1.999ApproxKCenterwithDisabilities([AnswerOf1_1]);

Set 1.999ApproxKCenter(Point[] p){//write your code for knapsack here}

Question 13: Based on your answer of Question 6, discuss why it is not possible to find a 1.999approximation algorithm for the 𝑘-center with disabilities problem.
Reference[1] D. P. Williamson and D. Shmoys, “The design of approximation algorithms”, Cambridge University
Press, 2011. Chapter 2.2[2] C. Y. Shen, H. H. Shuai, K. F. Hsu, and M. S. Chen, “Task-Optimized Group Search for Social
Internet of Things”, Proceedings of the 20th International Conference on Extending Database
Technology (EDBT’17), pages 108-119, 2017.

Important Points
1. The zones above are to give you an idea how competitive this class will be. They will havenothing to do with your final grade. At one of my classes, everyone who were in B and C
Zone at the midterm examination have got A from this class.
2. To obtain credits from this class, you must attend the final examination on July 16th.
3. After the final examination, those who do not get enough scores for the credits will be asked
to submit a report.