Uncapacitated facility location problem using local search
Not clear what is &quot;open the additional facility $i^*$&quot;.
Isn't $i^* \in S^*$ already open? Where does this facility open? in $S$? If so, why is it marked with a star? Doesn't that stand for the optimal solution?

As the proof explicitly says, $i^* \in S^* - S$. In words, it is a facility which is open in the optimal solution but not in the locally optimal solution.
The phrase &quot;open the additional facility $i^*$&quot; indicates modifying the locally optimal solution $S$ by opening the additional facility $i^*$. This is clear from context, sine as you write, $i^*$ is already open in $S^*$, but is closed in $S$.
The facility $i^*$ is marked with a star since that's how the author chose to name this variable. The name of the variable isn't important. That said, $i^*$ is chosen by taking some facility which is open in $S^*$ but not in $S$. That is, it is part of the optimal solution but not of the locally optimal one. So the notation makes sense to me. It is using the convention that stars denote parts of the optimal solution.

If the function returns the nearest facility in $S$, what is the meaning of choosing $i'$? Isn't it just one facility that is the closest in $S$? I mean isn't $R$ of size 1? (line 2)

The set $R$ consists of all facilities in $S^*$ whose closest facility in $S$ is $i$. If $S = \{i\}$, then $R = S^*$, and in particular, $R$ could contain more than one facility. Out of all facilities in $R$, we choose the one closest to $i$, and denote it $i'$.

What is $i^*$ in the second paragraph?

As the proof explicitly says, $i^*$ is an arbitrary element of $R$ different from $i'$.