A polynomial-time exact algorithm for the connected k-facility location problem on trees

This paper studies the Connected [Formula: see text]-Facility Location Problem (Con[Formula: see text]FLP) on trees. Let [Formula: see text] be an undirected tree, where [Formula: see text] is the [Formula: see text]-vertices set and [Formula: see text] is the [Formula: see text]-edges set. A facility set [Formula: see text] and a client set [Formula: see text] are given. Each client [Formula: see text] has one weight [Formula: see text] denoting the demand amount of [Formula: see text], and each facility [Formula: see text] has a weight [Formula: see text] denoting the opening cost at [Formula: see text], and each edge [Formula: see text], for [Formula: see text], is associated with a weight [Formula: see text] denoting the connection cost of it. When some facilities [Formula: see text] are opened, the overall cost involved in Con[Formula: see text]FLP includes three parts: the cost of opening facilities [Formula: see text], [Formula: see text] times the cost of Steiner tree interconnecting all the opened facilities where [Formula: see text] is a fixed parameter, and the total connection cost of assigning each client to the closest facility in [Formula: see text]. The goal of Con[Formula: see text]FLP is to open at most [Formula: see text] facilities to minimize the overall cost, for a given input parameter [Formula: see text]. This paper focuses on the case of Con[Formula: see text]FLP on trees where [Formula: see text], and as a result presents a polynomial-time exact dynamic programming algorithm and a computational experiment to illustrate it. Furthermore, a simple way is shown to adapt the algorithm to the general case of [Formula: see text] and [Formula: see text]. Finally, we apply the algorithm to a Con[Formula: see text]FLP instance in a regional tree-like water transportation network.