Now, we will re visit the uncapacitated facility location problem. Before we proceed new methodology for the uncapacitated facility location problem, we can extend some terminology for assignment costs between clients or facilities either. For example, assignment costs between client $i$ and $j$ can be the shortest path between client $i$ and $j$. If we define this as so, it is known to reserve the solution because of the metric closure.
Now, let’s recap the problem itself.
Minimize $\sum\limits_{i \in F}f_iy_i + \sum\limits_{i \in F, j \in D} c_{ij}x_{ij}$ such that
$\sum\limits_{i \in F}x_{ij} = 1$ $\forall j \in D$,
$x_{ij} \le y_i$ $\forall i \in F, j \in D$ and
$x_{ij}, y_i \in \{0, 1\}$ $\forall i \in F, j \in D$.
Then, we can do LP-relaxation below.
Minimize $\sum\limits_{i \in F}f_iy_i + \sum\limits_{i \in F, j \in D} c_{ij}x_{ij}$ such that
$\sum\limits_{i \in F}x_{ij} = 1$ $\forall j \in D$,
$x_{ij} \le y_i$ $\forall i \in F, j \in D$ and
$x_{ij}, y_i \ge 0$ $\forall i \in F, j \in D$.
With above, LP dual is like follow.
Maximize $\sum\limits_{j \in D} v_j$ such that
$w_{ij} \ge 0$ $\forall i \in F, j \in D$,
$\sum\limits_{j \in D}w_{ij} \le f_i$ $\forall i \in F$,
$v_j - w_{ij} \le c_{ij}$ $\forall i \in F, j \in D$.
Now let’s define some terminologies for a given dual solution $v^{\star}, w^{\star}$.
- Client $j$ is neighbor of facility $i$ if $v_{j}^{\star}$ $\ge$ $c_{ij}$. With that let denotes $N(i)$ as the set of neighbors of $i$.
- Client $j$ contributes to $i$ if $w_{ij}^{\star} > 0$.
Now, let’s desing the algorithm.
$S \leftarrow D$ // Left clients to be allocated
$T \leftarrow \emptyset$ // Facility which are open
$\operatorname{while}$ $S$ $\neq$ $\emptyset$
$\operatorname{if}$ some $j$ $\in$ $S$ neighbors some $i$ $\in$ $T$ // $j$ paid enough to assigned to facility $i$
$S \leftarrow S - N(i)$
$\operatorname{while}$ $T$ $\neq$ $\emptyset$
$T' \leftarrow T' \cup \{i\}$
$T \leftarrow T - \{h \in T : \exists j \in D, w_{ij} > 0 \text{ and } w_{hj} > 0\}$
Now, if $j$ doesn’t have a neighbor in $T’$ then there exists $i \in T’$ such that $c_{ij} \le 3v_j$ if we work with algorithm above. Let’s think about $T$ at the end of “$\operatorname{while}$ $S$ $\neq$ $\emptyset$” and $T’$ at the end of the algorithm. Then, all $j$’s neighbors will be excluded in $T$ at the loop of “$\operatorname{while}$ $T$ $\neq$ $\emptyset$” to be not exists in $T’$. Let denotes $h$ as the neighbor of $j$ which $v_j$ stops to increase. Notice that $h$ is not in $T’$ and $h$ should be a neighbor of $j$. Then, there exists some $k$ that contributes $h$ and $i$ $\in$ $T’$ for all $h$. First of all, if $j$ contributes to $i$ then $j$ is neighbor of $i$. If we think about the algorithm itself, we increase $w_{ij}$ only if $i$ $\in$ $N(j)$. As a result, $k$ need to be a neighbor of both $h$ and $i$. At the same time $j$ is a neighbor of $h$. Now, $c_{ij}$ $\le$ $c_{ik}$ $+$ $c_{hk}$ $+$ $c_{hj}$ from the triangle inequality. Then, $c_{ik}$ $+$ $c_{hk}$ $+$ $c_{hj}$ $\le$ $v_{k}$ $+$ $v_{k}$ $+$ $v_{j}$ because each of them are in the neighbor relation.
With above, $v_k$ $\le$ $v_j$ is true. Proof is like follow. Let’s assume not. $v_k, w_{hk}$ will stop increasing at the moment of between “$k$ neighbors $h$ $\in$ $T$” or “$h$ $\not\in$ $T$ become tight and $k$ neighbors $h$”. However we should select second case because $k$ can increase $w_{hk}$ only after $k$ neighbors $h$. At the same time, $v_j$ will stop increasing at the moment of between “$j$ neighbors $h$ $\in$ $T$” or “$j$ $\not\in$ $T$ become tight and $k$ neighbors $h$”. In the first case, $h$ $\in$ $T$ already but $k$ stoped increasing $v_k$ when $h$ become tight therefore $v_k$ $<$ $v_j$. In the second case, both $v_j$ and $v_k$ stop increasing at the same time. As a result $v_k$ $=$ $v_j$. Therefore claim holds.
Now, we can prove that this algorithm is a 3-approximation algorithm. Even though algorithm increase uniformly, we can just pick the smallest delta value of constraints to run this algorithm in polynomial time. With this, all other parts of algorithm are polynomial. Therefore, this algorithm runs in a polynomial time.
Now, let’s think about the solution that assigning $i$ to $j$ which $i$ that contributes to $j$ and assigning $i$ that doesn’t contributes to the facility in $T’$ to facility $j$ in $T’$ such that maximizes $v_j$. Notice that from the algorithm we forced it to contributes to only one facility or none of facility. Let’s define $A(i)$ $\subseteq$ $N(i)$ as the set of assigned clients to faciltiy $i$ which clients neighbors $i$ $\in$ $T$, $Z$ as the set of clients that doesn’t neighbors any $j$ $\in$ $T$ and $X(j)$ $\in$ $T’$ as the facility that client $j$ assigned for $j$ such that contributes none of $T’$. Notice that all of clients that contributes none of $T’$ will not be in $A(i)$ because it should neighbor of some in $T’$ if it contributes. At the same time, all of clients that contributes some of $T’$ will be in $A(i)$ because it should neighbor of some in $T’$. Then, total cost will be $\sum\limits_{i \in T’}(f_i + \sum\limits_{j \in A(i)}c_{ij})$ $+$ $\sum\limits_{j \in Z}c_{X(j)j}$. Then, $\sum\limits_{i \in T’}(f_i + \sum\limits_{j \in A(i)}c_{ij})$ $=$ $\sum\limits_{i \in T’}\sum\limits_{j \in A(i)}(w_{ij} + c_{ij})$ $=$ $\sum\limits_{i \in T’}\sum\limits_{j \in A(i)}v_{j}$. Notice that first equality comes from that $i$ $\in$ $T’$ $\subseteq$ $T$ and $T$ is the set of facility that become tight. At the same time, $w_{ij}$ $+$ $c_{ij}$ $=$ $v_j$ because $j$ is tight. Notice that $j$ is tight because $j$ will contributes to only one facility and $j$ will be assigned to there. Now, $\sum\limits_{j \in Z}c_{X(j)j}$ $\le$ $3\sum\limits_{j \in Z}v_{X(j)}$ if we pick $X(i)$ as the maximum possible one for $v_j$. Notice that we proved that “if $j$ doesn’t have a neighbor in $T’$ then there exists $i \in T’$ such that $c_{ij} \le 3v_j$”. Therefore, claim holds.