## Abstract

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^{2}n^{6}) for the absolute and O(ps^{2}n^{2}) for the node restricted problem, improving on the previous results by a factor of O(n^{3}). (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^{2}n^{4}) (absolute) and O(pk^{2}n^{2}) (node restricted) algorithms.

Original language | English |
---|---|

Pages (from-to) | 23-36 |

Number of pages | 14 |

Journal | Annals of Operations Research |

Volume | 191 |

Issue number | 1 |

DOIs | |

Publication status | Published - Nov 2011 |

## Keywords

- Dynamic programming
- Multifacility location problems
- Ordered median problem
- Tree networks