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(ps2n6) for the absolute and O(ps2n2) for the node restricted problem, improving on the previous results by a factor of O(n3). (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(pk2n4) (absolute) and O(pk2n2) (node restricted) algorithms.
- Dynamic programming
- Multifacility location problems
- Ordered median problem
- Tree networks