A quadratic time exact algorithm for continuous connected 2-facility location problem in trees

This paper studies the continuous connected 2-facility location problem (CC2FLP) in trees. Let $$T = (V, E, c, d, \ell , \mu )$$ be an undirected rooted tree, where each node $$v \in V$$ has a weight $$d(v) \ge 0$$ denoting the demand amount of v as well as a weight $$\ell (v) \ge 0$$ denoting the cost of opening a facility at v, and each edge $$e \in E$$ has a weight $$c(e) \ge 0$$ denoting the cost on e and is associated with a function $$\mu (e,t) \ge 0$$ denoting the cost of opening a facility at a point x(e, t) on e where t is a continuous variable on e. Given a subset $$\mathcal {D} \subseteq V$$ of clients, and a subset $$\mathcal {F} \subseteq \mathcal {P}(T)$$ of continuum points admitting facilities where $$\mathcal {P}(T)$$ is the set of all the points on edges of T, when two facilities are installed at a pair of continuum points $$x_1$$ and $$x_2$$ in $$\mathcal {F}$$ , the total cost involved in CC2FLP includes three parts: the cost of opening two facilities at $$x_1$$ and $$x_2$$ , K times the cost of connecting $$x_1$$ and $$x_2$$ , and the cost of all the clients in $$\mathcal {D}$$ connecting to some facility. The objective is to open two facilities at a pair of continuum points in $$\mathcal {F}$$ to minimize the total cost, for a given input parameter $$K \ge 1$$ . This paper focuses on the case of $$\mathcal {D} = V$$ and $$\mathcal {F} = \mathcal {P}(T)$$ . We first study the discrete version of CC2FLP, named the discrete connected 2-facility location problem (DC2FLP), where two facilities are restricted to the nodes of T, and devise a quadratic time edge-splitting algorithm for DC2FLP. Furthermore, we prove that CC2FLP is almost equivalent to DC2FLP in trees, and develop a quadratic time exact algorithm based on the edge-splitting algorithm. Finally, we adapt our algorithms to the general case of $$\mathcal {D} \subseteq V$$ and $$\mathcal {F} \subseteq \mathcal {P}(T)$$ .