Improved complexity results for several multifacility location problems on trees

In this paper we consider multifacility location problems on tree networks. On general networks, these problems are usually NP‐hard. On tree networks, however, often polynomial time algorithms exist; e.g., for the median, center, centdian, or special cases of the ordered median problem. We present an enhanced dynamic programming approach for the ordered median problem that has a time complexity of just O(ps ² n ⁶) for the absolute and O(ps ² n ²) for the node restricted problem, improving on the previous results by a factor of O(n ³). (n and p being the number of nodes and new facilities, respectively, and s (≤n) a value specific for the ordered median problem.) The same reduction in complexity is achieved for the multifacility k‐centrum problem leading to O(pk ² n ⁴) (absolute) and O(pk ² n ²) (node restricted) algorithms.