# fault-tolerant K-median problem on an undirected graph

We know that the K-median problem is proved to be NP-Hard. In fault-tolerant K-median problem on an undirected graph $$G=(V, E)$$:

We are given a set of facilities $$F\subseteq V$$ and a set of demands (or clients) $$D\subset V$$ in a metric space. We can open at most $$k$$ facilities and then assign each client $$j$$ to the $$r_j \geq 1$$ facility. Assigning demand $$j$$ to facility $$i$$ incurs an assignment cost of $$d(i, j)$$, where $$d(i, j)$$ is the shortest path between $$i$$ and $$j$$. Our goal is to minimize the sum of the assignment costs for all clients.

If $$r_j$$ is uniform, e.g. $$r_j=3$$ for all clients, each client should be connected to three facilities. Why the below algorithm does not solve the problem in polynomial time; let's assume $$r_j =3$$.

1. Go through all the vertices in $$F$$
• For each $$v \in F$$ Calculate the sum of the distance to all clients $$D$$
• Store this sum value in a variable
2. Select the first vertext $$v$$ with minimum sum variable as the first facility to be opened
3. Select the second vertex $$v'$$ with minimum sum variable as the second facility to be opened
4. Select the third vertex $$v''$$ with minimum sum variable as the third facility to be opened
5. Connect all clients to facilities calculated in steps 2,3,4.

Note: This problem was considered in this article , and the authors provided an approximation algorithm for it. Hence, it should be a hard problem. They did not specifically mention the problem to be solved on the graph but mentioned that it should be on metric space. Moreover, they mention the existence of an approximation algorithm even in the uniform case of $$r_j$$.

• It is very easy to find a counterexample for your algorithm. Simply try to prove if your algorithm gives optimal solution; you will hit some counterexample while proving it. Commented Jul 6, 2023 at 23:00
• Thank you for your comment. Would you provide small concrete example? @InuyashaYagami Commented Jul 7, 2023 at 10:29

Let the set of client locations is $$C = \{c_1,c_2,c_3\}$$ and the set of feasible facility locations is $$F = \{f_1,\dotsc,f_6\}$$. Let $$k = 5$$. Let the distance function be defined by $$3 \times 6$$ matrix $$D$$ such that $$D[i,j]$$ denotes the distance of client $$i$$ to facility $$j$$:
$$\begin{bmatrix} 1 & 1 & 2 & 1 & 3 & 3\\ 1 & 1 & 2 & 3 & 3 & 1\\ 1 & 1 & 2 & 3 & 1 & 3\\ \end{bmatrix}$$
Sum of distances for $$f_1$$ is $$3$$, for $$f_2$$ is $$3$$, for $$f_3$$ is $$6$$, for $$f_4$$ is $$7$$, for $$f_5$$ is $$7$$, and for $$f_6$$ is $$7$$.
Your algorithm chooses the facilities $$f_1$$, $$f_2$$, and $$f_3$$. The total cost of the clients is $$12$$.
However, the optimal solution is $$f_1$$, $$f_2$$, $$f_4$$, $$f_5$$, and $$f_6$$ with total cost $$9$$.