Improved complexity results for several multifacility location problems on trees

Jörg Kalcsics*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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(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.

Original languageEnglish
Pages (from-to)23-36
Number of pages14
JournalAnnals of Operations Research
Volume191
Issue number1
DOIs
Publication statusPublished - Nov 2011

Keywords

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

Fingerprint

Dive into the research topics of 'Improved complexity results for several multifacility location problems on trees'. Together they form a unique fingerprint.

Cite this