Facility Location Problem

Problem

Suppose we have a set of facilities $F$ and a set of clients $C$, and would like to open a subset of facilities to serve the clients. The cost consists of two parts:

1. one for opening the selected facilities;
2. one for connecting each client to its nearest facility.

Formally, denote $f_i$ the cost of facility $i \in F$ and $d_{u,i}$ the distance from a client $u \in C$ to a facility $i \in F$. Further, we assume that the distances satisfy the following constraint:

Let $S \subseteq F$ be a subset of facilities. The cost of $S$ is given by

The problem is to find a set $S$ that minimizes this cost.

Linear Programming

The linear program for the problem is given as follows:

The first constraint says that each client is assigned to at least one facility. The second one says that a facility must be (fractionally) open if there is a client assigned to it.

Weak Duality $\implies$ Dual Program

Let $\alpha_u$ be the dual variable associated with constraint (1) and $\beta_{u, i}$ be the one with constraint (2). We want the following inequalities, called weak duality, to hold:

When such inequalities hold, $\sum_{u \in C} \alpha_u$ constitutes a lower bound for cost of the primal program. The problem of obtaining a tightest such lower bound, under the constraints under which the above inequalities hold, gives the dual program:

Intuitive Explanation

Here we give a more intuitive way of deriving the dual. First, observe that $\sum_{u \in C} \min_{i \in F} d_{u,i}$ is a trivial lower bound of the primal programming. In this case, each client is assigned to its nearest facility. However we ignore facility cost entirely.

To incorporate the facility cost, for each facility $i$ we divide its cost $f_i$ among the clients, such that client $u$ needs to pay $\beta_{u, i}$ if it is assigned facility $i$. Note that $\beta_{u, i}$ can be arbitrary non-negative number as long as it satisfies that $\sum_{u \in C} \beta_{u, i} = f_i$ for all $i \in F$.

Theorem. For each subset $S \subseteq F$, let $\mu : C \rightarrow S$ be the function defined by

$$\mu_S (u) \doteq \underset{i \in S}{\arg \min}\, d_{u,i} \,.$$

We have

$$\begin{aligned} \sum_{u \in C} \left( d_{u, \mu_S (u)} + \beta_{u, \mu_S (u)} \right) \le \sum_{i \in S} f_i + \sum_{u \in C} d_{u, \mu_S (u)} \end{aligned}$$

Proof. It suffices to show that

But this is obviously true, since

$\square$

If we define

Then $\sum_{u \in C} \alpha_u$ constitutes a lower bound for the cost of each solution for the primal LP. In particular, it is a lower bound of the cost of the optimal integral solution $S^*$ (its corresponding assignment function is denoted as $\mu^*$):

The problem of determining a set of $\beta_{u, i}$'s that maximizes the lower bound $\sum_{u \in C} \alpha_u$ gives the dual program.

Complementary Slackness

Let $x^*, y^*$ and $\alpha^*, \beta^*$ be the optimal primal and dual solutions, respectively. For these set of variables, weak duality holds with equalities. By complementary slackness, it holds that

1. $\alpha^*_u = 0$ or $\sum_{i \in F} x^*_{u, i} = 1$
2. $\beta^*_{u, i} = 0$ or $y^*_i - x^*_{u, i} = 0$

and

3. $\alpha^*_u - \beta^*_{u, i} = d_{u,i}$ or $x^*_{u, i} = 0$
4. $\sum_{u \in C} \beta^*_{u, i} = f_i$ or $y^*_i = 0$

Deterministic Rounding [1]

$4$-Approximation Algorithm

We show how to pick a good subset $S \subset F$ based on the optimal solutions $x^*, y^*$, $\alpha^*$ and $\beta^*$.

First we construct a graph $G = (V, E)$ based on the $x^*$.

Definition. A derived graph from the optimal LP consists of the follows:

1. The vertex set $V = F \cup C$;
2. The undirected edge set $E = \{ (u, i) : x^*_{u, i} > 0, \forall i \in F, u \in C\}$, i.e., the edge set $E$ consists of client-facility pairs $(u, i)$ for which $x^*_{u, i} > 0$.

In the graph $G$, the neighbors a client $u \in C$ can only be facilities.

Definition. For each $u \in C$, let $N(u)$ be the set of facilities adjacent to $u$ in $G$.

Similarly, we define two-hop neighbors of a client $C$, as the client who connects to $u$ via a intermediate facility.

Definition. For a client $u \in C$, its two hop neighbors are the set of clients $v$ whose distance to $u$ is at most $2$:

$$N^2(u) = \{ v \in C: N(u) \cap N(v) \neq \emptyset \}.$$

Note that $u \in N^2(u)$.

Below is an example. The cycles represent clients and the squares are for facilities. Associated each client and each facility are the $\alpha_u^*$ value and opening cost respectively.

An important property of this graph is that

Property. If $(u, i) \in E$, then $x^*_{u, i} >0$, which implies that $\alpha^*_u =d_{u,i} + \beta^*_{u, i}$ by complementary slackness. It concludes that $\alpha^*_u \ge d_{u,i}$ if there is an edge $(u, i)$ in $G$.

The following is the first constant factor approximation algorithm for the un-capacitated facility location problem, proposed in 1997 [1].

Algorithm 1

1. $S \leftarrow \emptyset$
2. $U \leftarrow C;\, B \leftarrow \emptyset$
3. while $U \neq \emptyset$ do
4. $\quad$ $u \leftarrow \underset{v \in U}{\arg \min \,} \,\alpha^*_v$
5. $\quad$ $i_u \leftarrow \underset{i \in N(u)}{\arg \min \,} \,f_i$
6. $\quad$ $U \leftarrow U \setminus N^2(u)$
7. $\quad$ $B \leftarrow B \cup \{ u \}$
8. $\quad$ $S \leftarrow S \cup \{ i_u \}$

It is important that at each iteration, when a client $u$ is chosen, all vertices clients in $N^2(u)$ are removed from $U$. This guarantees that clients in $B$ has non-overlapping neighbors, i.e.,

Consider the assignment scheme in which, instead of assigning each client to its nearest facility in $S$, at each iteration, we assign clients in $N^2(u)$ to the chosen facility $i_u$. Then each iteration of the algorithm creates a clusters, which contains three kinds of vertices:

1. The selected client $u$ with minimum $\alpha^*_u$.
2. All $u$'s neighboring facilities.
3. All un-assigned clients neighboring to these facilities.

Such clusters are non-overlapping.

The example above shows one iteration of the algorithm. The vertex with minimum value of $\alpha^*_u$ (i.e. 1) is opened, highlighted by the red cycle. There are two facilities connected to it, the cheap opening cost of which is $1$. Then all un-assigned clients neighboring these two facilities are assigned to the cost 1 facility, as shown by the purple dashed arrows.

It is left to analyze the cost of the solution returned.

Theorem. The facility cost of Algorithm $1$ is at most OPT.

Proof.

At each iteration, a client $u$ is selected. In the primal LP, constraint (1) requires that

Note that although $u$ can assigned to a facility fractionally, the total amount of assignment must be at least $1$. Further, although a facility can be fractionally open in primal LP, the constraint (2)

implies that the open amount must be at least the amount a client assign to it. We conclude that

The neighbor sets $N(u)$'s of the selected clients $u \in B$ are disjoint.

Therefore, summing over $u \in B$, the total facility cost is bounded by

Theorem. The connection cost of Algorithm $1$ is at most $3 \cdot$OPT.

Proof. Now we analyze the assignment cost.

Case One. If $u \in B$, then it is selected by the algorithm, and $i_u \doteq \arg \min_{i \in N(u)} f_i$ belongs to $S$. Therefore,

Case Two. If $v \notin B$, then $v \in N^2(u)$ for some $u \in B$. Since $v \in N^2(u)$, there exists some facility $j \in N(v) \cap N(u)$. By triangle inequality, we have

The last inequality holds since $\alpha^*_u \le \alpha^*_v$.

$\square$

Combing assignment cost and facility cost, Algorithm $1$ is $4$-approximation.

How happy are we with the $4$-approximation algorithm? Probably not. In the previous example, when a facility is opened, only one client contributes to its opening cost. However, in the primal solution, many other clients assigned to it do not contribute to the opening cost, which implies that the current analysis may not be tight.

Randomized Rounding [3]

$3$-Approximation Rounding

In the section, we improve the approximation ratio of $4$ to an expected value of $3$. In the previous rounding, we bound the opening cost as

which is not tight.

Define the assignment cost for client $u$ in the optimal primal LP solution as $A_u = \sum_{i \in F} x^*_{u, i} d_{u,i}$. Indeed, it is affordable to bound

It is possible to devise a randomized rounding algorithm that incorporates this cost and improve the approximation ratio to $3$. The only differences compared to the first rounding algorithm are

1. We pick a client that minimize $\alpha^*_u + A_u$;
2. We pick a facility with probability $x^*_{u, i}$.

Below is the algorithm.

Algorithm 2

1. $S \leftarrow \emptyset$
2. $U \leftarrow C;\, B \leftarrow \emptyset$
3. while $U \neq \emptyset$ do
4. $\quad$ $u \leftarrow \underset{v \in U}{\arg \min \,} \,\big( \alpha^*_v + A_v \big)$
5. $\quad$ $\Pr[ i_u \leftarrow i ] = x^*_{u, i}, \quad \forall i \in N(u)$
6. $\quad$ $U \leftarrow U \setminus N^2(u)$
7. $\quad$ $B \leftarrow B \cup \{ u \}$
8. $\quad$ $S \leftarrow S \cup \{ i_u \}$

Facility Cost

The analysis of expected facility cost is almost the same as before. It is guaranteed that

Therefore, the expected opening cost is bounded by

Connection Cost

Now we analyze the assignment cost.

Case One. If $u \in B$, then

Case One. If $v \notin B$, then there exists $u \in B$, s.t., $v \in N^2(u)$. Then there exists some facility $j \in N(u) \cap N(v)$. By triangle inequality, the expected connection cost is at most

Total Cost

The cost is at most

Remark: there is still room for improvement. When a client $u$ is selected and a facility $i$ is sampled, $v \in N^2(u)$ is assigned to $i$. On the other hand, $v$ itself may contributes to the opening cost of some other facility not open. To make the expected opening cost tight, we may consider opening facilities directly with respect to probability $y^*_i$.

$(1 + 3/e)$-Approximation Rounding [3]

In the previous analysis, we see that a facility may be under-sampled. There are two reasons for this:

1. For a facility $i$, $\exists u \in N(i)$ such that $u \in B$. When $u$ is selected, facility $i$ is sampled with probability $x^*_{u, i}$, which might be smaller than $y^*_i$.

2. For a facility $i$, none of its clients $u \in N(i)$ is selected, therefore $i$ is never sampled.

To fix theses issues and based on Algorithm $2$, we have the following algorithm. The algorithm presented here is a modified version of the one proposed in [3], but guided the same philosophy.

Algorithm 3:

1. $T \leftarrow F$
2. $k \leftarrow 0$
3. $S_1, S_2, S_3 \leftarrow \emptyset$
4. while there exists un-assigned client do
5. $\quad$ $k \leftarrow k + 1$
6. $\quad$ Let $u_k$ be the unassigned one with smallest $\alpha^*_u$
7. $\quad$ Open exactly one facility $i_k \in N( u_k )$ with probability $x^*_{u, i}$
8. $\quad$ $S_1 \leftarrow S_1 \cup \{ i_k \}$
9. $\quad$ For each $i \in N(u_k) - \{ i_k \}$
10. $\qquad$ Open $i$ with probability $(y^*_{i} - x^*_{u, i} ) / ( 1- x^*_{u, i} )$
11. $\qquad \quad$ $S_2 \leftarrow S_2 \cup \{ i \}$
12. $\quad$ $T \leftarrow T - N(u_k)$
13. $\quad$ Assign $v$ to $i_k$, for each $v \in N^2( u_k )$
14. for each facility $i \in T$
15. $\quad$ Open $i$ with probability $y^*_i$
16. $\qquad$ $S_3 \leftarrow S_3 \cup \{ i \}$
17. Re-assign each $u \in C$ to its nearest open facility.

When the algorithm stops, denote $S = S_1 \cup S_2 \cup S_3$ the set of open facilities and $B = \{u_1, u_2, ..., u_{|B| } \}$ the set of selected clients by line $6$. The following lemma shows that Algorithm $3$ fully samples each facility and therefore never loses to Algorithm $1$.

Facility Cost

Lemma 1. For each $i \in F$, it is opened with probability $y^*_i$.

Proof. Note the facilities are not open independently. The claim is trivially true if a facility is is sampled in line 10. Otherwise, $\exists u \in B$, s.t., $i \in N(u)$. The probability of $i$ being open is

$\blacksquare$

Corollary. By linearity of expectation, the expected facility opening cost is $\sum_{i \in F} y^*_i f_i$.

Connection Cost

What is not trivial is the analysis of the assignment cost. Given $S$, assigning $u \in C$ to its nearest facility in $S$ minimizes the assignment cost. To bound this cost, we investigate a sub-optimal assignment based on $S$. For each $u \in C$ we select a subset $S(u) \subseteq S$ and assign it to a closest facility in $S(u)$. This leads to a possibly increase in the expected assignment cost.

Let $Z$ be the random variable of the assignment cost for client $u$ and $X_i$ ($i \in N(u)$) be the indicator random variable of $i$ being in $S(u)$. As when none of the facility in $N(u)$ is selected into $S(u)$, then assignment cost is bounded by $3 \cdot \alpha^*_u$, the value of $Z$ is therefore at most

The goal is to provide a method for generating $S(u)$, such that

1. $\Pr[X_i = 1] = x^*_{u, i}$, for $\forall i \in N(u)$;
2. $\Pr[\mathbb{I}_{[ X_i = 0, \forall i \in N(u)]} = 1 ] \le 1/e$.

Any such generation method satisfies to bound the assignment cost of client $u$:

Note that the inequality here may not be tight, as we replace the $\min$ operation into $\sum$. But it suffices to prove the expected approximation ratio. When combined with the expected facility opening cost, we know that total expected cost is bounded by

The $S(u)$ is generated as follows. If $u \in B$, then we let $S(u) = S$. Otherwise, we initialize $S(u)$ with $S - N(u)$, and for facility $i \in N(u) \cap S$, we perform some carefully designed operations to ensure that $\Pr[i \in S(u) ]= x^*_{u, i}$.

1. If $i \in S_3$, we keep it in $S(u)$ with probability $\frac{x^*_{u, i} } {y^*_i}$. Therefore,$$\Pr[i \in S(u)] = \Pr[i \in S(u) \mid i \in S] \cdot \Pr[i \in S] = x^*_{u, i}$$
2. Otherwise, $\exists u_k \in B$, such that $i \in N(u_k)$. There are two possible cases

   1. Case 1: $x^*_{i,u_k} \ge x^*_{u, i}$, the probability of selecting $i$ is defined as follows:

      $$\Pr[i \in S(u) \mid i \in S] = \begin{cases} \begin{array}{lr} {x^*_{u, i} } / { x^*_{i,u_k} }, &i \in S_1 \\ 0, & i \in S_2 \end{array} \end{cases}$$

      Therefore,

      $$\begin{array}{ll} \Pr[i \in S(u)] &= \Pr[i \in S(u) |i \in S_1 ] \cdot \Pr[ i \in S_1 ] + \Pr[i \in S(u) |i \in S_2 ] \cdot \Pr[ i \in S_2 ] \\ &= x^*_{u, i} / x^*_{i,u_k} \cdot x^*_{i,u_k} \\ &= x^*_{u, i} \end{array}$$

   2. Case 2: $x^*_{i,u_k} < x^*_{u, i}$, the probability of selecting $i$ is defined as follows:

      $$\Pr[i \in S(u) \mid i \in S] = \begin{cases} \begin{array}{lr} 1, &i \in S_1 \\ (x^*_{u, i} - x^*_{i, u_k} ) \cdot ( 1 - x^*_{i,u_k } ) / (y^*_{i} - x^*_{i,u_k } ), & i \in S_2 \end{array} \end{cases}$$

      The probability is well defined as $y^*_i \ge x^*_{u, i}$. It follows

      $$\begin{array}{ll} \Pr[i \in S(u)] &= \Pr[i \in S(u) |i \in S_1 ] \cdot \Pr[ i \in S_1 ] + \Pr[i \in S(u) |i \in S_2 ] \cdot \Pr[ i \in S_2 ] \\ &= x^*_{i,u_k} + (x^*_{u, i} - x^*_{i, u_k} ) \cdot ( 1 - x^*_{i,u_k } ) / (y^*_{i} - x^*_{i,u_k } ) \cdot (y^*_{i} - x^*_{i,u_k } ) / (x^*_{u, i} - x^*_{i, u_k} )\\ &= x^*_{u, i} \end{array}$$

It is left to show that $\Pr[\mathbb{I}_{[ X_i = 0, \forall i \in N(u)]} = 1 ] \le 1/e$. For $u \in B$, this holds trivially. If not, we prove the following lemma.

Lemma 2. For any client $u \in C \setminus B$, the probability that none of facility in $N(u)$ belongs to $S(u)$ is bounded by $1/ e$.

Proof.

Observe that

constitutes a partition of $F$. For any client $u$, define $R_k = N(u_k) \cap N(u)$, where $1 \le k \le |B|$. Further, let $R_{|B| + 1} = T \cap N(u)$. Then $\{ R_k \}_{k \in [|B| + 1]}$ is a partition of $N(u)$.

Consider facilities in $N(u_k)$ ($k \in [|B|]$). The probability of none of them being in $S(u)$ is

The relation holds even if $R_k = \emptyset$, in which $\sum_{i \in R_k} x^*_{u, i} = 0$.

For $k = |B| + 1$, the probability that none of the facility in $R_k$ is sampled is given by

Therefore, taking product over all the events, we know that

$\blacksquare$

Primal-Dual Algorithm [2]

In this section we show a primal-dual algorithm that is purely combinatorial.

1. Initially we have a set of dual variables $\alpha_u, u \in C$ and $\beta_{u,i}, u \in C, i \in F$ that are set to $0$. Note that they are feasible.

2. Then we try to optimize this set of variables by increasing all $\alpha_u, u \in C$ in parallel until some $\alpha_u$'s are blocked.

Why are they blocked? Because the dual constraint

becomes tight for some client $u \in C$. If we increase $\alpha_u$ further, the variables are no longer dual feasible. However, we can modify our strategy by increasing these $\beta_{u,i}$ simultaneously with $\alpha_u$ until facility $i$ is blocked, i.e.,

Definition. For each facility $i \in F$, define its neighbors $N(i)$ as to be the clients such that $\alpha_u \ge d_{u,i}$.

The algorithm for constructing the dual variables are given as follows.

Algorithm. Increasing the Dual

1. $U \leftarrow C$: the set of un-blocked clients.
2. $B \leftarrow \emptyset$: the set of blocked facilities.
3. while $U \neq \emptyset$ do
4. $\quad$ For $\forall u \in U$
5. $\qquad$ Increase all $\alpha_u$ (if necessary, $\beta_{u,i}$ for some $i$ ) simultaneously
6. $\quad$ Until either
7. $\qquad$ some facility $i \notin B$ is blocked:
8. $\qquad\quad$ $B \leftarrow B \cup \{i \}$
9. $\qquad\quad$ $U \leftarrow U \setminus N(i)$
10. $\qquad$ some client $u$ neighbors a blocked facility $i \in B$:
11. $\qquad\quad$ $U \leftarrow U \setminus \{ u \}$

Question to Ponder. What is the running time for the Dual Variable Increment algorithm.

After running the algorithm above, we get a set of maximal variables which we can't simultaneously increase any more. It has the following property

Property. Each client $u \in C$ neighbors at least one block facility.

If not, the algorithm will not stop since $U$ is not empty.

Next, we show how to construct an approximate solution from the maximal dual variables. First we construct a graph $G = (V, E)$ based on the dual LP.

1. The vertex set $V = B \cup C$.
2. The edge set $E = \{ (u, i) : \alpha_u \ge d_{u,i}, u \in C, \forall i \in B \}$.

Moreover, if $\beta_{u,i} > 0$ for some $i \in F$, $u \in C$, we say that $u$ contributes to $i$.

Definition. For each facility $i \in F$, let $N^+(i)$ be set of clients contributing to it.

Algorithm. Facility Selection

1. $S \leftarrow \emptyset$.
2. while $B \neq \emptyset$ do
3. $\quad$ Let $i \in B$ be the earliest blocked facility.
4. $\quad$ $S \leftarrow S \cup \{ i \}$
5. $\quad$ // Remove all facilities $i'$ if $\exists u \in C$ that contributes to both $i$ and $i'$.
6. $\quad$ $B \leftarrow B \setminus \{ i' \in B : N^+(i) \cap N^+(i') \neq \emptyset \}$.