Finite dominating sets for the multi-facility ordered median problem in networks and algorithmic applications

Research output: Journal article publicationJournal articleAcademic researchpeer-review

7 Citations (Scopus)

Abstract

We identify a finite dominating set (FDS) for a special case of the multi-facility ordered median problem in networks, in which the λ-weights can take at least two different values. This FDS result not only includes the FDS research for the p-center problem, but also extends the case of a < b in the λ-weights provided by Kalcsics et al. (Kalcsics, J., Nickel, S., Puerto, J. (2003). Multi-facility ordered median problems: A further analysis. Networks, 41(1), 1-12). Furthermore, based on the FDS result, we devise an exact algorithm for the problem. In addition, we present a polynomial time algorithm for the problem with at most three different values in the λ-weights in tree networks. Finally, we pose an open problem on identifying the existence of a polynomial size FDS for the multi-facility convex ordered median problem in networks.
Original languageEnglish
Pages (from-to)707-712
Number of pages6
JournalComputers and Industrial Engineering
Volume57
Issue number3
DOIs
Publication statusPublished - 1 Oct 2009

Keywords

  • Algorithms
  • Finite dominating sets
  • Multi-facility ordered median problem
  • Pseudo-equilibria

ASJC Scopus subject areas

  • Computer Science(all)
  • Engineering(all)

Cite this