I’m studying about UFLP using the book The Design of Approximation Algorithms Ch 9 starting page 233 (there is an electronic free edition), I ran into some unclear steps in the book and need some help with it.

In few words the UFLF deals with finding a subset of facilities from a given set of potential facility locations to meet the demands of all the customers such that the sum of the opening cost for each of the opened facilities and the service cost (or connection cost) is minimized

We can do the following local steps on current solution

1. We can open one additional facility an “add” move

2. We can close one facility that is currently open a “delete” move

3. We can do both of these simultaneously a “swap” move

Let’s assume we have optimal solution and let S* be it’s open

**What I need help with :**

Proof from the book page 235 :

Not clear what is “open the additional facility i*”

isn’t i* in S* already open ? where does this facility open ? in S ? if so why its marked with * isn’t it for the optimal solution ?

**I also need help with :**

proof from page 237

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)

There is a typo and it’s not lemma 9.3 but lemma 9.1 in the second par, my second question here is also similar to the first question what is i* here ?

Any clarification will be happily welcome, thank you