Multi-facility ordered median problems in directed networks

Research output: Journal article publicationJournal articleAcademic researchpeer-review

3 Citations (Scopus)

Abstract

This paper uses a finite dominating set (FDS) to investigate the multi-facility ordered median problem (OMP) in a strongly connected directed network. The authors first prove that the multi-facility OMP has an FDS in the node set, which not only generalizes the FDS result provided by Kalcsics, et al. (2002), but also extends the FDS result from the single-facility case to the multiple case, filling an important gap. Then, based on this FDS result, the authors develop an exact algorithm to solve the problem. However, if the number of facilities is large, it is not practical to find the optimal solution, because the multi-facility OMP in directed networks is NP-hard. Hence, we present a constant-approximation algorithm for the p-median problem in directed networks. Finally, we pose an open problem for future research.
Original languageEnglish
Pages (from-to)61-67
Number of pages7
JournalJournal of Systems Science and Complexity
Volume24
Issue number1
DOIs
Publication statusPublished - 1 Feb 2011

Keywords

  • Algorithms
  • finite dominating sets
  • multi-facility ordered median problem
  • pseudo-equilibria

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • Information Systems

Cite this