Multifacility ordered median problems on networks: A further analysis

Abstract

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.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 39 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.