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 )$$ T = ( V , E , c , d , ℓ , μ ) be an undirected rooted tree, where each node $$v \in V$$ v ∈ V has a weight $$d(v) \ge 0$$ d ( v ) ≥ 0 denoting the demand amount of v as well as a weight $$\ell (v) \ge 0$$ ℓ ( v ) ≥ 0 denoting the cost of opening a facility at v, and each edge $$e \in E$$ e ∈ E has a weight $$c(e) \ge 0$$ c ( e ) ≥ 0 denoting the cost on e and is associated with a function $$\mu (e,t) \ge 0$$ μ ( e , t ) ≥ 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$$ D ⊆ V of clients, and a subset $$\mathcal {F} \subseteq \mathcal {P}(T)$$ F ⊆ P ( T ) of continuum points admitting facilities where $$\mathcal {P}(T)$$ 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$$ x 1 and $$x_2$$ x 2 in $$\mathcal {F}$$ F , the total cost involved in CC2FLP includes three parts: the cost of opening two facilities at $$x_1$$ x 1 and $$x_2$$ x 2 , K times the cost of connecting $$x_1$$ x 1 and $$x_2$$ x 2 , and the cost of all the clients in $$\mathcal {D}$$ D connecting to some facility. The objective is to open two facilities at a pair of continuum points in $$\mathcal {F}$$ F to minimize the total cost, for a given input parameter $$K \ge 1$$ K ≥ 1 . This paper focuses on the case of $$\mathcal {D} = V$$ D = V and $$\mathcal {F} = \mathcal {P}(T)$$ F = 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$$ D ⊆ V and $$\mathcal {F} \subseteq \mathcal {P}(T)$$ F ⊆ P ( T ) .