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.