Multifacility Ordered Median Problems on Networks: A Further Analysis

Jörg Kalcsics, Stefan Nickel, Justo Puerto*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish
Pages (from-to)1-12
Number of pages12
JournalNetworks
Volume41
Issue number1
DOIs
Publication statusPublished - Jan 2003

Keywords

  • Algorithms
  • Complexity
  • Finite dominating sets
  • Location theory

Fingerprint

Dive into the research topics of 'Multifacility Ordered Median Problems on Networks: A Further Analysis'. Together they form a unique fingerprint.

Cite this