Multifacility ordered median problems on networks: A further analysis

✍ Scribed by Jörg Kalcsics; Stefan Nickel; Justo Puerto

• Publisher: John Wiley and Sons
• Year: 2002
• Tongue: English
• Weight: 191 KB
• Volume: 41
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.10053

✦ Synopsis

Abstract

In this paper, we address the ordered p‐median problem, which includes as special cases most of the classical multifacility location problems discussed in the literature. Finite dominating sets (FDS) are known for particular instances of this problem: p‐median, p‐center, and p‐centdian. We find an FDS for the ordered p‐median problem. This set allows us to gain a better insight into the general FDS structure of network location problems. This FDS is later used to present the first polynomial time algorithm for p‐facility ordered median problems on tree networks. This result is combined with some approximation algorithms to give an O(log M log log M) approximate solution of these problems on general networks, where M is the number of vertices. © 2002 Wiley Periodicals, Inc.