# Uncapacitated facility location problem using local search

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:

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 its open facilities, and let $$\sigma^*$$ denote the corresponding optimal assignment of clients to open facilities. To compare the cost of this optimal solution to the current, locally optimal solution of the algorithm, we let $$F$$ and $$F^*$$ denote, respectively, the total facility cost of the current solution and the optimal one, and similarly let $$C$$ and $$C^*$$ denote their respective total assignment costs. The optimal value OPT is clearly $$F^*+C^*$$. Note that now $$F$$ stands for both the set of facilities and the cafility cost of the current solution, but the meaning at any given point should be clear from the context.

What I need help with:

Lemma 9.1: Let $$S$$ and $$\sigma$$ be a locally optimal solution. Then $$C \leq F^* + C^* = \mathrm{OPT}.$$

Proof from the book page 235:

Consider some facility $$i^* \in S^* - S$$, and suppose that we open the additional facility $$i^*$$, and reassign to that facility all of the clients that were assigned to $$i^*$$ in the optimal solution: that is, we reassign all clients $$j$$ such that $$\sigma^*(j) = i^*$$. Since our current solution $$S$$ and $$\sigma$$ is locally optimal, we know that the additional facility cost of $$i^*$$ is at least as much as the improvement in cost that would result from reassigning each client optimally to its nearest open facility; hence, $$f_{i^*}$$ must also be more than the improvement resulting from our specific reassignments; that is, $$f_{i^*} \geq \sigma_{j\colon \sigma^*(j) = i^*} (c_{\sigma(j)j} - c_{\sigma^*(j)j}).$$

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 is it marked with a star? Doesn't that stand for the optimal solution?

I also need help with:

Proof from page 237:

Let $$\phi(i^*)$$ denote the facility in $$S$$ closest to $$i^*$$.

Lemma 9.3: Let $$S$$ and $$\sigma$$ be a locally optimal solution. Then $$F \leq F^* + 2C^*.$$

Consider a facility $$i$$ that is not safe (or, in other words, is unsafe), and let $$R \subseteq S^*$$ be the (non-empty) set of facilities $$i^* \in S^*$$ such that $$\phi(i^*) = i$$; among those facilities in $$R$$, let $$i’$$ be the one closest to $$i$$. We will derive one inequality for each member of $$R$$, based on an add move for each member of $$R - \{i’\}$$, plus one swap move closing the facility at $$i$$, while opening a facility at $$i’$$.

First let us derive an inequality for each add move corresponding to $$i^* \in R - \{i’\}$$. As in the proof of Lemma 9.3, we open a facility at $$i^*$$, and for each client $$j$$ that is assigned to $$i$$ in the locally optimal solution and is assigned to $$i^*$$ in the optimal solution, we reassign client $$j$$ to $$i^*$$. The change in cost caused by this move must also be non-negative, and we derive the inequality $$f_{i^*} + \sum_{j\colon \sigma(j) = i \text{ & } \sigma^*(j)=i^*} (c_{\sigma^*(j)j}-c_{\sigma(j)j}) \geq 0.$$

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 paragraph, my second question here is also similar to the first question: what is $$i^*$$ here?

Any clarification will be happily welcome.

• Have you taken an "intro to proofs" class? It seems you might have to start with some easier proofs, to get accustomed to the format and concept of proofs. – Yuval Filmus Jun 2 '20 at 7:44
• @YuvalFilmus thanks for the editing and the comment, I acutely did a long way with some advance proofs. I don't why this one confused me a bit, but after a second more deep reading it was fine. I'll leave the post as clarification if someone else needs it. – Jackson Jun 5 '20 at 8:20

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 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 "open the additional facility $$i^*$$" 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'$$.